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

 이 문제는 슬라이딩 윈도우와 맵을 이용해서 풀었다. elements 의 최대 길이가 1,000 이므로, 최대 O(n^2) 시간을 소요할 수 있고 그 이상의 시간이 드는 알고리즘은 사용할 수 없다. 만약 부분 수열의 합을 구하는 알고리즘 내부를 단순 반복문으로 구성하면 1,000,000 * (l 값) 이 들어 시간이 초과될 것 같았고, 이를 보완하기 위해 고정된 범위를 이용한 슬라이딩 윈도우로 시간을 단축시켰다. 

 

 또한 값의 중복이 없어야 하므로 map에 해당 값을 저장함으로써 중복을 없앴다. set을 사용할 수도 있지만 아직 잘 몰라서 잘 알고 있는 map을 이용해 문제를 풀었다.

 

 

 

 

 

#include <string>
#include <vector>
#include <map>

using namespace std;

map<int, bool> mp;

int solution(vector<int> elements) {
    int answer = 0;    
    
    int initAcc = 0;
    // 부분 수열 크기가 1인 경우, n인 경우
    for (int e : elements) {
        mp[e] = true;
        initAcc += e;
    }
    mp[initAcc] = true;
    
    // 부분 수열 크기가 2 ~ n - 1 까지인 경우
    int size = elements.size();
    
    for (int l = 2; l <= size - 1; l++) {
        int left = 0;
        int right = l - 1;
        int acc = 0;
        int cnt = size;
        
        // init
        for (int i = left; i <= right; i++) {
            acc += elements[i];
        }
        
        cnt--;
        
        while (cnt >= 0) {
            acc -= elements[left++];
            left %= size;
            right++;
            right %= size;
            acc += elements[right];
            
            mp[acc] = true;
            cnt--;
        }
    }
    
    answer = mp.size();
    
    return answer;
}