[프로그래머스] 2단계 - 연속 부분 수열 합의 개수

1. 문제 설명

원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수 return

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

프로그래머스

 

2. 문제 풀이법

queue를 사용하면 쉽게 풀 수 있다

 

만일 예시고 [7, 9, 1, 1, 4]라는 수가 들어오면 

- 길이가 1인 연속 부분 수열의 합 [7, 9, 1, 1, 4]

- 길이가 2인 연속 부분 수열의 합 [16, 10, 2, 5, 11]

... 이런식으로 연속 부분 수열의 합이 나오는데 잘 보면 queue를 사용해서 풀 수 있도록 되어있다

 

길이가 2인 연속 부분 수열의 합이 왜 저렇게 나왔는지 보자면

[(7 + 9), (9 + 1), (1 + 1), (1 + 4), (4 + 7)] 이렇게 값이 나온 것이다

배열의 맨 뒤까지 숫자가 도달하면 다시 앞으로 가서 연산해주면 된다

그 부분을 queue로 구현한 것이다

원하는 길이 만큼 queue에다가 원소를 담아주고, 한번에 더해주면 연속 부분 수열의 합을 구할 수 있다

 

이때 초과되는 인덱스를 처리해주어야 하는데 다시 위의 예제를 보자면 (4 + 7)은 인덱스 4와, 인덱스 0이다

인덱스 0은 다시 말하면, 인덱스 4에서 하나 증가된 것이므로 인덱스 5와 같다

즉 '(현재 인덱스 + 현재 길이) % 원소의 갯수' 를 해주면 인덱스의 범위를 초과하지 않고 처리할 수 있다

 

3. 소스 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(vector<int> elements) {
    int answer = 0;
    
    vector<int> v;
    for (int i = 1; i <= elements.size(); i++) {
        queue<int> q;
        for (int j = 0; j < elements.size(); j++) {
            for (int k = 0; k < i; k++) {
                int idx = (j + k) % elements.size() ;
                q.push(elements[idx]);    
            }
            
            int sum = 0;
            while (!q.empty()) {
                sum += q.front();
                q.pop();
            }
            v.push_back(sum);   
        }
    }
    
    sort(v.begin(), v.end());
    
    for (int i = 1; i < v.size(); i++) {
        if (v[i] == v[i - 1] && i != v.size() - 1)
            continue;
        answer++;
    }
    
    return answer;
}CPP