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

프로그래머스

 

📄 문제

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
부분 수열의 합은 k입니다.
합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

 

📝 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer {0, 1000000};
    
    for(int i = sequence.size() - 1; i >= 0; --i)
    {
        int sum = 0;
        
        for(int j = i; j >= 0; --j)
        {
            sum += sequence[j];
            
            if(sum == k && i - j <= answer[1] - answer[0])
            {
                answer[1] = i;
                answer[0] = j;
                break;
            }
            else if(sum > k)
            {
                break;
            }
        }
    }
    
    return answer;
}

• 시간초과가 난 풀이법으로, 현재 인덱스부터 sum과 같아지거나, 커지기 전까지 값을 더하여 계산을 하는 단순한 방법입니다.
• 하지만 문제에서 sequence의 길이는 1,000,000이기에 O(N^2)으로 문제를 해결할 수 없습니다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    
    vector<int> answer {0, 1000000};
    int p1 = 0, p2 = 0;
    int sum = 0;
    
    for(int i = 0; i < sequence.size(); ++i)
    {
        // p1은 먼저 나아가며 더함
        sum += sequence[p1++];
        
        // 만약 p1만큼 더한 값이 k보다 크다면?
        if(sum > k)
            while(sum - sequence[p2] >= k) // sum이 k 이하가 될때까지
                sum -= sequence[p2++]; // p2를 증가시키며 값을 빼줌
        if(sum == k) // 만약 sum == k일때
            if(answer[1] - answer[0] > p1 - 1 - p2) // p1과 p2의 간격이 answer보다 작다면?
                answer = { p2, p1 - 1 }; // 정답을 갱신 (연속된 수열의 길이가 짧음)
    }
    
    return answer;
}

• 투포인터를 사용하여 합의 누적을 갱신하여 문제를 해결하는 방법으로 접근하였습니다.
• sum이 k보다 커진다면, 값을 지우는 p2를 이용하여 한칸씩 앞으로 이동하며 sum을 갱신합니다.
• sum이 k와 같다면, 조건을 비교하여 answer을 갱신할 수 있습니다.