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

문제

 

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

프로그래머스

 

 

문제풀이

elements크기만큼 벡터를 선언하고, 변수 두 개를 선언하여 하나는 벡터 인덱스 변수, 다른 하나는 1씩 증가시켜 숫자를 고르는 인덱스로 선언했다.

 

첫 줄은 idx2 = 0 이므로 바로 숫자를 저장한다.

그다음은 idx2 = 1이므로 한 칸 오른쪽의 숫자를 저장한다.

그다음은 idx2 = 2이므로 두 칸 오른쪽의 숫자를 저장한다.

벡터의 크기-1만큼 반복한다.

7+9+1+1+4 나 9+1+1+4+7 은 같은 수 이므로 전체의 합은 한 번만 구하면 된다.

그리고 set을 이용하여 값을 구하면 바로 insert 한다.

마지막으로는 중복이 제거된 set의 크기를 출력하면 된다.

 

코드

#include <string>
#include <vector>
#include <set>
using namespace std;

int solution(vector<int> elements) {
    int idx(0), idx2(0);
    set<int>answer;
    vector<int>sum(elements.size());

    for (idx = 0; idx + 1 < elements.size(); ++idx) {
        for (idx2 = 0; idx2 < elements.size(); ++idx2) {
            sum[idx2] += elements[(idx + idx2) % elements.size()];
            answer.insert(sum[idx2]);
        }
    }
    answer.insert(sum[0] + elements.back());

    return answer.size();
}