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

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

풀이

sequence 길이가 1,000,000 이기 때문에 한번의 반복문으로 해결해야 하는 문제입니다.

따라서, 투포인터 알고리즘을 사용하면 연속된 부분수열의 합을 한번의 반복문으로 해결할 수 있습니다.

 

오랜만에 사용하는 알고리즘이라 기억이 안나 2중 for loop으로 구현했다가 시간초과가 나서 결국 알고리즘을 찾아보고 구현했습니다.

 

정답을 리턴할 때 부분수열의 길이가 가장 짧은 것이 정답이 되므로, 우선순위큐를 사용해서 1. 길이순, 2. 길이가 같다면 인덱스 순 으로 정렬하도록 했습니다. 

 

리뷰

while loop를 도는데 segment error 가 자꾸 떠서 1시간 정도를 날렸습니다. right는 초기화를 하고 left 변수를 초기화를 하지 않았더니 발생했던 문제였습니다. 초기화를 잘하자...!

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct Info 
{
    int length = 0;
    vector<int> index;
    
    Info(int a, int b, int c) {
        length = a;
        index.push_back(b);
        index.push_back(c);
    }
    
    bool operator<(Info a) const {
        if (length == a.length)
            return index[0] > a.index[0];
        return length > a.length;
    }
};

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int left = 0 , right = 0;
    int partial_sum = sequence[left];
    priority_queue<Info> pq;

    while (left<=right && right < sequence.size())
    {
        if (partial_sum < k) partial_sum += sequence[++right];
        else if (partial_sum == k) {
            pq.push(Info(right-left, left ,right));
            partial_sum -= sequence[left++];
        }
        else {
            partial_sum -= sequence[left++];
        }
    }
        
    return pq.top().index;
}

시간 초과 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct Info 
{
    int length = 0;
    vector<int> index;
    
    Info(int a, int b, int c) {
        length = a;
        index.push_back(b);
        index.push_back(c);
    }
    
    bool operator<(Info a) const {
        if (length == a.length)
            return index[0] > a.index[0];
        return length > a.length;
    }
};

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int left = 0;
    int prev_length = 100000;
    priority_queue<Info> pq;
    for (left = 0; left < sequence.size(); left++) {
        int sum = 0; // 부분 수열 합
        int length = 0;
        for (int right = left; right < sequence.size(); right++) {
            sum += sequence[right];
            length = right - left;
            if (length > prev_length) break;
            if (sum == k) {
                // cout << left<< " " << right << " " << length << " " << sum << endl;
                pq.push(Info(length, left, right));
                prev_length = length;
            }
            else if (sum > k) break;
            else
                continue;
        }
    }
    // cout << pq.top().length << endl;
    return pq.top().index;
}