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

연속 부분 수열 합의 개수

문제 링크

연속 부분 수열 합의 개수

분석

연속된 부분 수열의 합을 구해야합니다.

중복된 값은 제외해야합니다.

elements의 뒤에 elements를 또 붙이면 원형 수열과 유사하게 표현이 가능합니다.

풀이

#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> elements) {
    int answer = 0;
    // 중복을 제거한 합을 저장할 자료구조 사용
    unordered_set<int> sumSet;

    // i는 부분 수열의 길이
    for (int i = 1; i <= elements.size(); ++i)
    {
        // j는 배열의 시작 위치
        for (int j = 0; j < elements.size(); ++j)
        {
            // 합을 저장할 변수
            int sum = 0;
            
            // 합을 구할 반복문
            for (int k = 0; k < i; ++k)
            {
                // 원형 수열에 대해 인덱스로 처리한 방법
                sum += elements[(j + k) % elements.size()];
            }
            
            // 합 저장
            sumSet.insert(sum);
        }
    }
    
    return answer = sumSet.size();
}

브루트 포스로 원래 배열을 이어붙이지 않고 인덱스로 처리한 방법입니다.

성능 요약

시간 복잡도는 $O(n^3)$입니다.

• 부분 수열의 길이에 대한 반복문 $O(n)$
• 부분 수열의 시작 위치에 대한 반복문 $O(n)$
• 부분 수열의 합을 구하는 반복문 $O(n)$
• $O(n \times n \times n)$

공간 복잡도는 $O(n^2)$입니다.

• 중복되지 않은 부분 수열의 합을 저장하는 unordered_set에서 모든 부분 수열의 값이 다를 경우 $O(n^2)$

테스트 1 〉 통과 (0.01ms, 4.16MB)
테스트 2 〉 통과 (28.54ms, 4.98MB)
테스트 3 〉 통과 (91.46ms, 6.53MB)
테스트 4 〉 통과 (216.77ms, 7.43MB)
테스트 5 〉 통과 (399.90ms, 10.1MB)
테스트 6 〉 통과 (717.10ms, 11.5MB)
테스트 7 〉 통과 (1094.19ms, 16.9MB)
테스트 8 〉 통과 (1649.55ms, 16.9MB)
테스트 9 〉 통과 (2291.42ms, 18.7MB)
테스트 10 〉 통과 (3199.86ms, 20.3MB)
테스트 11 〉 통과 (551.19ms, 11MB)
테스트 12 〉 통과 (693.10ms, 11.4MB)
테스트 13 〉 통과 (918.48ms, 12.5MB)
테스트 14 〉 통과 (1102.16ms, 16.8MB)
테스트 15 〉 통과 (1374.60ms, 17MB)
테스트 16 〉 통과 (1631.92ms, 17MB)
테스트 17 〉 통과 (1947.86ms, 18MB)
테스트 18 〉 통과 (2297.06ms, 18.7MB)
테스트 19 〉 통과 (2670.78ms, 19.5MB)
테스트 20 〉 통과 (3066.70ms, 20.3MB)