[Programmers] 연속 부분 수열 합의 개수

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

프로그래머스

문제 설명

1부터 원소 개수까지 연속되는 수열의 합에 대해서 중복없이 총 개수를 구하는 문제이다. 처음에는 큐를 활용하여 풀려고 했으나 시간 초과가 발생했었다. 그래서 방법을 찾던 중 기존 배열을 2배로 늘리는 방법이 있었고 이를 활용했다.

[4, 7, 9, 1, 1] 이라는 배열이 있다고 하자. 이 배열을 0부터 길이 - 1만큼의 부분을 뒤에다 붙이면 원형 탐색을 하는 것처럼 사용할 수 있다. 이 배열은 [4, 7, 9, 1, 1, 4, 7, 9, 1]이 될 것이다. 여기서 순회하는 순서를 0부터 1씩 증가시키고 탐색 범위를 시작 순서 + 원소 개수로 하면 원형 큐처럼 배열을 탐색할 수 있다.

for (int start = 0; start < elements.length; start++) {
    int sum = 0;
    for (int k = start; k < start + elements.length; k++) {
        sum += newElements[k];
        set.add(sum);
    }
}

위 방식으로 배열을 탐색하면 아래와 같다.

1. [4], [7], [9], [1], [1]
2. [7, 9], [9, 1], [1, 1], [1, 4], [4, 7]
3. [9, 1, 1], [1, 1, 4], [1, 4, 7], [4, 7, 9], [7, 9, 1]
4. [1, 1, 4, 7], [1, 4, 7, 9]
5. [1, 4, 7, 9, 1]

코드

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int[] newElements = new int[elements.length * 2];
        
        for(int i = 0; i < elements.length; i++) {
            newElements[i] = newElements[i + elements.length] = elements[i];
        }
        
        Set<Integer> set = new HashSet<>();
        
        for (int start = 0; start < elements.length; start++) {
            int sum = 0;
            for (int k = start; k < start + elements.length; k++) {
                sum += newElements[k];
                set.add(sum);
            }
        }
        
        return set.size();
    }
}