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

문제

프로그래머스

 

원형으로 나열된 수열의 부분합 수를 구하는 문제이다.

 

나의 풀이 전략

set 자료형을 사용하여 부분합의 중복을 막는다.

 

상세

1) elements에서 합연산을 출발할 지점을 for 문으로 구축한다.

for (int start = 0; start < elements.size(); ++start) // 현재단계
{

}

 

2) 부분합의 길이를 1에서부터 elements의 길이까지를 for 문으로 구축한다.

for (int start = 0; start < elements.size(); ++start)
{
    for (int length = 1; length <= elements.size(); ++length) // 현재단계
    {

    }
}

 

3) 부분합을 저장해둘 변수 sum을 선언, 0으로 초기화해둔다.

elements를 for 문으로 탐색하여 sum에다 더해나간다.

sum이 구해지면 set<int> 자료형인 sumSet에 넣어둔다. (이렇게 하면 중복방지)

for (int start = 0; start < elements.size(); ++start)
{
    for (int length = 1; length <= elements.size(); ++length)
    {
    	// 현재단계
        int sum = 0;

        for (int i = start; i < start + length; ++i)
        {
            sum += elements[i%elements.size()];
        }

        sumSet.insert(sum);
    }
}

 

4) sumSet의 크기를 answer로 저장한다.

answer = sumSet.size();

return answer;

 

전체 소스코드

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

set<int> sumSet;

int solution(vector<int> elements)
{
    int answer = 0;

    for (int start = 0; start < elements.size(); ++start)
    {
        for (int length = 1; length <= elements.size(); ++length)
        {
            int sum = 0;

            for (int i = start; i < start + length; ++i)
            {
                sum += elements[i%elements.size()];
            }

            sumSet.insert(sum);
        }
    }

    answer = sumSet.size();

    return answer;
}

int main()
{
    cout << solution({7,9,1,1,4});
    return 0;
}