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

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

프로그래머스

 

 

문제 설명

철호는 수열을 가지고 놀기를 좋아합니다. 그는 자연수로 이루어진 원형 수열에서 연속하는 부분 수열의 합으로 만들 수 있는 숫자가 몇 가지나 되는지 궁금해졌습니다. 일반적인 수열에서는 앞과 뒤가 끊어져 있지만, 원형 수열에서는 처음과 끝이 연결된 수열이기 때문에, 더 많은 부분 수열을 만들 수 있습니다.

주어진 수열 elements에서 연속 부분 수열의 합으로 만들 수 있는 모든 경우의 수를 구하는 문제입니다.

접근 방식

1. 원형 수열에 대한 처리 → 주어지는 배열을 한번 더 이어 붙이면 된다
2. 부분 합에 대한 처리 → sliding window 를 사용하여 처리
3. 중복에 대한 처리 → unordered_set 을 사용하여 처리

코드

#include <bits/stdc++.h>
using namespace std;

unordered_set<int> s;

int solution(vector<int> elements) {
    vector<int> v = elements;
    for(int i = 0; i<elements.size(); i++){
        v.push_back(elements[i]);
    }

    for(int length = 1; length <= elements.size(); length++){
        int sum = 0;
        for(int i = 0; i<length; i++){
            sum += v[i];
        }
        s.insert(sum);

        for(int i = 1; i<elements.size(); i++){
            sum -= v[i-1];
            sum += v[i + length - 1];
            s.insert(sum);
        }
    }
    return s.size();
}