[프로그래머스] 연속된 부분 수열의 합 C++

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

이번 문제는 투 포인터 문제였습니다.

 

 

 

 

 

 

📝 문제 풀이

1. 구하려는 부분 수열의 처음 위치 s와 마지막 위치 e를 각각 0으로 초기화

2. 부분 수열의 합을 sequence[0]으로 초기화 (sequence[0]은 부분 수열 합의 최솟값)

3. 부분 수열의 길이는 sequence.size() + 1로 설정 (부분 수열 길이의 최댓값은 sequence.size()이기 때문에)

4. sum < k ➡️ 마지막 위치 e를 1 증가시킨 후, sum에 마지막 위치 e의 값을 더함 (아직 k보다 작으므로)

5. sum == k ➡️ 각 상황에 따라 result를 갱신. sum에서 처음 위치 s의 값을 뺀 후, 처음 위치 s를 1 증가 

6. sum > k ➡️ sum에서 처음 위치 s의 값을 뺀 후, 처음 위치 s를 1 증가

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    int s = 0, e = 0;
    int sum = sequence[0]; // 부분 수열의 합
    int subLen = sequence.size() + 1; // 부분 수열의 길이
    pair<int, int> result; // 부분 수열의 시작 인덱스와 마지막 인덱스를 담은 객체
    
    while (s <= e && e < sequence.size()) {
        if (sum < k) sum += sequence[++e];
        else if (sum == k) {
            if (e-s+1 < subLen) { // 길이가 더 짧은 수열이면
                subLen = e-s+1;
                result = {s, e};
            } else if (e-s+1 == subLen) {
                if (s < result.first) { // 시작 인덱스가 더 작으면
                    result = {s, e};
                }
            }
            
            sum -= sequence[s++];
        } 
        else sum -= sequence[s++];
    }
    
    return {result.first, result.second};
}

 

프로그래머스 - 결과 화면