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

프로그래머스

원형 수열의 모든 원소를 입력 받을 때, 원형 수열의 연속 부분 수열합으로 만들 수 있는 수의 개수를 구해주세요.

 

ex) 7, 9, 1, 1, 4

길이가 1인 부분 수열 -> 1, 4, 7, 9
길이가 2인 부분 수열 -> 2, 5, 10, 11, 16
길이가 3인 부분 수열 -> 6, 11, 12, 17, 20
길이가 4인 부분 수열 -> 13, 15, 18, 21
길이가 5인 부분 수열 -> 22

총-> 18개

 

풀이 방법

중복되는 수가 나올 수 있는 경우를 생각해줘야 합니다.

중복을 애초에 제거해주는 set으로 수를 관리하면 이 부분은 쉽게 해결됩니다. 

set<int> s;
for (int len = 1; len <= elements.size(); len++)
{
    for (int i = 0; i < elements.size(); i++)
    {
        int num = 0;
        int j = i;

        for (j = i; j < i + len; j++)
            num += elements[j % elements.size()];

        s.insert(num);
    }
}

수열의 합을 구해줄 때는 위처럼 항상 N번 반복하여 길이를 구하게 되면 시간 초과가 발생할 위험이 있습니다.

 

 

정답 코드

#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 num = 0;
        for (int j = i; j < i + elements.size(); j++)
        {
            num += elements[j % elements.size()];
            s.insert(num);
        }
    }
    
    return s.size();
}