Lv.2 / 연속 부분 수열 합의 개수

문제

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

프로그래머스

---

 

코드

#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> elements) {
    unordered_set<int> answer;
    
    for(int i=0; i<elements.size(); i++) {
        int sum = 0;
        for(int j=0; j<=i; j++) {
            sum += elements[j];
        }
        
        int left = 0, right = i;
        while(left < elements.size()) {
            answer.insert(sum);
            
            sum -= elements[left++];
            right = (right + 1) % elements.size();
            sum += elements[right];
        } 
    }    
    
    return answer.size();
}

---

 

풀이

1개부터 전체 길이만큼까지 반복하면서 수행한다.

 

각 갯수마다 초기 sum 값을 구해준다.

그 후, left 와 right 를 잡아 한 칸씩 전진하면서 수행하는데 이 때, 원형 수열이므로 right 는 처음으로 되돌아갈 수 있다. left 는 처음으로 되돌아갈 경우 중복된 결과를 반복하는 것이기에 수열의 마지막 항에 도착하면 종료한다.