[프로그래머스] 연속 부분 수열 합의 개수(Java)

문제

길이가 N인 원형 수열이 주어졌을 때, 길이 1부터 N까지 가능한 연속 부분 수열의 합을 모두 구하고, 그 중 서로 다른 값의 개수를 구하는 문제.

🛠 사용 기술

• 배열 슬라이딩 기법
• 누적합(Prefix Sum)
• HashSet을 통한 중복 제거

---

Approach 1 ⭕

🔍 접근법

모든 구간 길이(1 ~ N)에 대해 순회하며 (i + j) % N를 이용해 원형 수열을 처리하고, 모든 합을 HashSet에 저장해 중복을 제거했다.

• 간단하지만 3중 루프 → 시간 복잡도: O(N³)
• 입력 크기가 작기 때문에 통과되었지만, 대형 데이터에는 부적합

💻 코드

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();
        
        for(int z=1; z<=elements.length; z++){
            for(int i=0; i<elements.length; i++){
                int sum = 0;
                for(int j=0; j<z; j++){ //오프셋
                    sum += elements[(i+j)%elements.length];
                }
                set.add(sum);
            }
        }

        int answer = set.size();
        return answer;
    }
}

Approach 2 ⭕

🔍 접근법

효율적인 부분합 계산을 위해 원형 수열을 두 배로 확장한 뒤, 누적합(Prefix Sum)을 활용하였다. 이를 통해 각 구간의 합을 O(1)에 계산할 수 있다.

• 시간 복잡도: O(N²)
• 효율성, 안정성, 가독성 모두 만족

기존의 방법은 3중 for문이므로 최악의 경우에는 시간초과가 발생할 수 있을 거 같았다. lv2 수준에서는 타임 아웃이 발생하지 않아서 다행. 문제를 풀면서 DP를 이용해 푸는 방법도 생각해봤는데, 다음과 같이 배열을 복사해 2배로 늘리고, 각 구간별 누적 합을 구해두면 조금 더 시간 단축을 시킬 수 있다. 원리는 간단하다. 현재 인덱스의 누적 합은 이전 인덱스의 누적합 + 원본 배열의 인덱스에 해당하는 값이다. 그리고 구간 길이에 따라 필요한 누적값을 가져와서 빼주면 해당 구간에 해당하는 누적 합을 구할 수 있다.

💻 코드

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();
        int n = elements.length;
        
        // 1. 배열 2배로 확장
        int[] extended = new int[n*2];
        for(int i=0; i<n*2; i++){
            extended[i] = elements[i%n];
        }
        
        // 2. 누적 합 구해놓기
        int[] sum = new int[2*n];
        sum[0] = elements[0];
        for(int i=1; i<2*n; i++){
            sum[i] = sum[i-1] + extended[i];
        }
        
        // 3. 시작, 끝 인덱스에 해당하는 누적 값 빼주기
        for(int i=1; i<=n; i++){
            for(int j=0; j<n; j++){
                int result = sum[j+i] - sum[i];
                set.add(result);
            }
        }

        int answer = set.size();
        return answer;
    }
}

---

느낀 점 및 메모 💡

• 시간 복잡도 최적화를 위해 누적합과 배열 확장을 활용하는 것은 실무에서도 흔히 사용되는 테크닉이다.
• Prefix Sum을 사용하면 반복적인 구간합 계산을 O(1)로 줄일 수 있어 구간 합 문제에서 매우 강력한 도구임을 다시금 느꼈다.
• 향후에도 원형 수열이나 연속 구간 문제에서 두 배 확장 + 누적합 조합을 적극적으로 활용해야겠다.

---