<프로그래머스 C++> 원형 수열의 연속 부분 수열 합 풀이 (set)

문제

원형 수열에서 연속하는 부분 수열의 합으로 만들 수 있는 수가 몇 가지인지 구하는 문제이다.

원형 수열은 처음과 끝이 연결된 형태이다. (n번째 다음이 바로 0번째로)

---

풀이 아이디어

각 시작점에서 1, 2, 3개 ... n개까지 늘려가면서 합을 전부 구해 set에 넣는다.

i=0 (7이 시작점)
  7
  7+9
  7+9+1
  7+9+1+1
  7+9+1+1+4

i=1 (9가 시작점)
  9
  9+1
  9+1+1
  9+1+1+4
  9+1+1+4+7  ← 원형으로 7까지
  ...

원형 배열에서 끝을 넘어 처음으로 돌아오는건 %(element.size())로 처리한다.

 

i=3, len=3: (3+2) % 5 = 0 → elements[0] = 7  ← 원형으로 돌아옴

set이 중복을 자동으로 제거해주기 때문에 마지막에 sums.size()만 반환하면 된다.

---

문제 풀이

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

int solution(vector<int> elements) {
    int n = elements.size();
    set<int> sums;

    for(int i = 0; i < n; ++i)
    {
        int sum = 0;
        for(int len = 1; len <= n; ++len)
        {
            sum += elements[(i + len - 1) % n];
            sums.insert(sum);
        }
    }
    return sums.size();
}

---

코드 흐름

1. 시작점 순회

for(int i = 0; i < n; ++i)
{
    int sum = 0;

i는 부분 수열의 시작점을 의미한다. i가 바뀔때마다 sum을 0으로 초기화한다.

 

2. 길이별 합을 누적

for(int len = 1; len <= n; ++len)
{
    sum += elements[(i + len - 1) % n];
    sums.insert(sum);
}

len이 늘어날수록 sum에 다음 원소를 누적한다.

 

i=0 기준
len=1: sum = 7           → 1개짜리 합
len=2: sum = 7+9 = 16    → 2개짜리 합
len=3: sum = 16+1 = 17   → 3개짜리 합
len=4: sum = 17+1 = 18   → 4개짜리 합
len=5: sum = 18+4 = 22   → 5개짜리 합

매 단계마다 sums.insert(sum)으로 각 자릿수별 경우의 수 합을 set에 넣는다.

 

3. 원형 인덱스 처리

elements[(i + len - 1) % n]

배열 끝을 넘어가면 % n으로 자동으로 처음 항으로 넘어가도록 한다.

i=3 기준
len=1: (3+0)%5 = 3 → elements[3] = 1
len=2: (3+1)%5 = 4 → elements[4] = 4
len=3: (3+2)%5 = 0 → elements[0] = 7  ← 원형!
len=4: (3+3)%5 = 1 → elements[1] = 9
len=5: (3+4)%5 = 2 → elements[2] = 1

 

4. 결과 반환

return sums.size();

set이 중복을 자동으로 제거해주기 때문에 sums의 크기를 반환하면 이것이 서로 다른 합의 개수이다.

---

핵심 포인트

 

• 각 시작점에서 길이를 1씩 늘려가며 합을 누적하면 모든 연속 부분 수열 합을 구할 수 있다.
• (i + len - 1) % n으로 원형 배열에서 끝을 넘어 처음으로 돌아오는 것을 처리한다.
• set이 중복을 자동 제거하므로 별도의 중복 처리 없이 size()만 반환하면 된다.