연속 부분 수열 합의 개수/C++

프로그래머스

길이가 len인 연속 부분 수열의 합을 모두 구해서 set을 통해 중복을 제거 한 후 set의 크기를 리턴하면 된다.

 

먼저 연속 부분 수열의 합을 모두 구한다고 할 때, 예시로 [7,9,1,1,4]로 이루어진 원형 수열이 있으면 길이가 len인 연속 부분 수열의 합의 종류는 아래와 같다.

len = 1	7	9	1	1	4
len = 2	16	10	2	5	11
len = 3	17	11	6	12	20
len = 4	18	15	13	21	21
len = 5	22	22	22	22	22

이를 자세히 보면 idx = i로 시작하는 연속 부분 수열들은 idx = 0의 값에 idx = len의 값을 순차적으로 더해준 값이다.

	idx = 0	idx = 1	idx = 2	idx = 3	idx = 4
len = 1	7	9	1	1	4
len = 2	16	10	2	5	11
len = 3	17	11	6	12	20
len = 4	18	15	13	21	21
len = 5	22	22	22	22	22

즉, 해당 표의 값들은 tmp에 elements[(index + len) % elements.size()]을 반복적으로 더해줌으로써 구할 수 있다.

 

1. set 자료구조 선언

2. 이중 for문을 통해 tmp = 0에 elements[(j + i) % elements.size()]의 값을 elements.size()번 더해주고, 더할 때마다 s에 삽입한다.

3. 반복문이 끝나면 s.size()를 리턴

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(vector<int> elements) {
    set<int> s;

    for (int i = 0 ; i < elements.size() ; i++) {
        int tmp = 0;
        for (int j = 0 ; j < elements.size() ; j++) {
            tmp += elements[(j + i) % elements.size()];
            s.insert(tmp);
        }
    }

    return s.size();
}