프로그래머스, C++) Lv 2. 연속 부분 수열 합의 개수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131701?language=cpp

프로그래머스

 

슬라이딩 윈도우 기법 

-> 슬라이딩 윈도우라는 것을 알았지만, 구현을 실패,, -> GPT 도움

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

/*
슬라이딩 윈도우 적용
*/

int solution(vector<int> elements) {
    int n = elements.size();
    unordered_set<int> sums;
    
    // 1) 원형 처리: 배열을 2배로 확장
    vector<int> arr(2 * n);
    for (int i = 0; i < 2 * n; ++i) arr[i] = elements[i % n];

    
    for (int len = 1; len <= n; ++len) {
        // 1) 첫 윈도우 합: [0, len)
        int cur = 0;
        for (int i = 0; i < len; ++i) cur += arr[i];
        sums.insert(cur);

        // 2) 시작점 l = 1..n-1로 한 칸씩 밀면서 갱신
        for (int l = 1; l < n; ++l) {
            // 새로 포함될 오른쪽 원소: arr[l + len - 1]
            // 빠질 왼쪽 원소: arr[l - 1]
            cur += arr[l + len - 1];
            cur -= arr[l - 1];
            sums.insert(cur);
        }
    }
    return (int)sums.size();
}