프로그래머스 - 연속된 부분 수열의 합 (C++)

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

프로그래머스

 

 이번 문제는 비내림차순으로 정렬된 수열과 숫자 k가 주어질 때, 가능한 부분 수열 중 부분 수열 총 합이 k와 일치하면서 그 길이가 가장 짧은 부분 수열을 구하는 문제이다. 이 문제는 단순하게 길이가 1일 때부터 수열의 길이까지, 가능한 모든 부분 수열을 체크해도 답을 구할 수는 있을 것이다. 하지만 배열의 길이가 최대 1,000,000이기에 최악의 경우에는 매우 많은 시간이 걸릴 것이다. 그리고 실제로도 대략 반 정도가 시간 초과였다.

 그렇기에 다른 방법을 구해야 한다. 이 경우 적절한 알고리즘은 투 포인터(Two Pointer)이다. 투 포인터 알고리즘을 간단하게 얘기하자면, 왼쪽, 오른쪽 기준점을 정한 후 조건에 따라 각 기준점을 오른쪽으로 이동시키면서 문제를 해결하는 알고리즘이다. 예를 들어, 이 문제는 이런 흐름일 것이다.

1. 왼쪽 기준점, 오른쪽 기준점은 각각 부분 수열의 시작 인덱스, 끝 인덱스이다.
2. 왼쪽 기준점과 오른쪽 기준점을 0으로 둔다. (부분 수열이 길이가 1이면서 시작 인덱스와 끝 인덱스 모두 0일 때) 그리고 합은 sequence[0]으로 설정한다.
3. 반복문을 이용하면서 가능한 부분 수열을 검사한다. 이 때, 반복문은 왼쪽 기준점 <= 오른쪽 기준점 and 오른쪽 기준점 < sequence 길이일 때 반복한다.
   1. 만약 현재 합이 k보다 작을 경우, 오른쪽 기준점을 오른쪽으로 한 칸 옮긴다. (끝 인덱스의 값을 +1한다.) 그리고 옮긴 후, 옮긴 후의 끝 인덱스에 해당하는 값을 합에 더한다.
   2. 만약 현재 합이 k보다 작을 경우, 왼쪽 기준점에 해당하는 값을 합에서 뺀 후, 왼쪽 기준점을 오른쪽으로 한 칸 옮긴다. (시작 인덱스의 값을 +1한다.) 이 때, 왼쪽 기준점 >= 오른쪽 기준점이 될 수도 있다. 이럴 경우에 오른쪽 기준점의 값을 왼쪽 기준점의 값으로 설정한 후, 합도 다시 수정한다.
   3. 만약 현재 합이 k와 일치할 경우, 저장된 답 부분 수열의 길이와 현재 부분 수열의 길이를 비교한 후, 답을 갱신한다. 그리고 왼쪽 기준점을 오른쪽으로 옮긴다.

 

이런 과정을 거쳐서 문제의 조건을 충족시키는 부분 수열을 구할 수 있다. 아래는 이 과정을 코드로 옮긴 것이다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    // 답에는 최악의 경우를 상정(가능한 가장 긴 수열, 즉 처음부터 끝까지)
    answer.push_back(0);
    answer.push_back(sequence.size() - 1);  
    
    int leftIdx = 0;    // 투 포인터의 왼쪽
    int rightIdx = 0;   // 투 포인터의 오른쪽
    long long sum = sequence[leftIdx];  // 연속된 부분 수열의 합
    
    while(leftIdx <= rightIdx && rightIdx < sequence.size())
    {   
        // 합이 k보다 같거나 클 때 (두 경우 공통으로 해야할 게 있다.)
        if (sum >= k)
        {
            // 만약 합이 k와 같을 경우
            if (sum == k)
            {   
                int len = rightIdx - leftIdx;
                int answerLen = answer[1] - answer[0];
            
                // 답을 갱신할 수 있으면 갱신한다.
                // 현재 저장된 답보다 현재 길이가 더 짧을 경우 갱신
                if (answerLen > len)
                {
                    answerLen = len;
                    answer[0] = leftIdx;
                    answer[1] = rightIdx;
                } 
            }

            // 왼쪽 포인터의 위치를 +1 한다.
            sum -= sequence[leftIdx++];
            
            // 왼쪽 포인터가 오른쪽 포인터의 오른쪽에 있을 경우
            // 오른쪽 포인터의 위치와 합을 갱신한다.
            if (leftIdx > rightIdx)
            {   
                rightIdx = leftIdx;
                sum = sequence[rightIdx];
            }
        }
        else    
        {
            // 합이 k보다 작은 경우
            // 오른쪽 포인터의 위치를 +1 한다.
            sum += sequence[++rightIdx];
        }
    }
    
    return answer;
}