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

문제

제한 사항

예시

---

풀이

#include <vector>
#include <algorithm>

int solution(vector<int> elements) {
    vector<int> summary;

    for (int i = 0; i < elements.size(); i++) {
        int sum = 0;
        for (int j = i; j < i + elements.size(); j++) {
            int index = j % elements.size();
            sum += elements[index];
            summary.push_back(sum);
        }
    }

    sort(summary.begin(), summary.end());
    summary.erase(unique(summary.begin(), summary.end()), summary.end());

    int answer = summary.size();
    return answer;
}

 

문제의 핵심이라고 파악한 두가지는

1. 최대 인덱스를 넘겨도 다시 처음부터 인덱스를 카운트하는 원형 배열의 합 구하기

2. 중복 제거

이렇게 였다.

 

먼저 예시를 보면 알 수 있듯이 연속 부분 수열의 합을 구하는 가짓수는 길이가 1부터 elements 전체까지, 총 element.size()만큼 반복되어 이를 for문을 이용해 돌린다.

길이가 1인 경우, 길이가 2인 경우 ... 를 따지게 된 것이고, 이 안에서 다시 합의 경우의 수를 구해야하므로 이중 for문을 사용해주었다.

 

int index = j % elements.size();

 

내부 for문 인덱스로 나머지값을 구해 첫번째 핵심인 '최대 인덱스를 넘겨도 다시 처음부터 인덱스를 카운트' 를 실행할 수 있도록 하였다.

이를 통해 배열이 [7, 9, 1, 1, 4] 일 때, 4부터 시작하는 3개 수의 합을 구한다 하더라도 배열을 넘어가지 않고 [4, 7, 9] 를 도출해낼 수 있게 된다.

 

이렇게 구한 값을 sum 변수에 넣고, 이 값을 다시 summary에 push 해준다.

 

마지막 중복 제거와 같은 경우는 answer을 구하기 전에 <algorithm>의 sort(), unique(), erase()를 활용하여 중복을 제거할 수 있도록 하였다.

 

이중 for문이 끝나고 나면 summary는 무차별적으로 값이 할당된 배열의 상태가 된다.

이를 sort()를 통해 오름차순 정렬을 먼저 진행해 중복값을 근접한 인덱스로 몰아주고, 제거의 과정으로 unique() 와 erase()를 사용한다.

 

이 내용은 다음 게시글을 참고하였다.

https://kkaeruk.tistory.com/19