연속 부분 수열 합의 개수_복습

2026.07.18

문제 풀이

나의 코드

소요 시간: 22분
시간 복잡도: $O(n^3)$

---

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();
        
        for (int i = 0; i < elements.length; i++) { // 더할 수의 개수
            for (int j = 0; j < elements.length; j++) { // 시작할 인덱스
                int cnt = 0;
                int sum = 0;
                int idx = j;
                while(cnt < i + 1) {
                    sum += elements[idx];
                    idx = (idx + 1) % elements.length;
                    cnt++;
                }
                set.add(sum);
            }
        }
        return set.size();
    }
}

AI 코드

시간 복잡도: $O(n^2)$

---

코드 분석

원형 전개
인덱스 연산 없이 접근 가능

슬라이딩 윈도우
배열이나 문자열에서 연속된 구간을 한 칸씩 옮겨가며
필요한 값을 효율적으로 갱신하는 기법

오른쪽으로 한 칸 이동할 때, 빠지는 왼쪽 값을 빼고 새로 들어오는 값을 더함

arr = [7, 9, 1, 1, 4, 7, 9, 1, 1, 4]

// 2번 연속하는 수를 더하는 경우
16 - 7(현재 더한 수의 왼쪽 수) + 1(다음에 포함되는 수) = 10(9 + 1)
10 - 9 + 1 = 2
2 - 1 + 1 = 2
.
.
.

---

import java.util.Set;
import java.util.HashSet;

class Solution {
	public int solution(int[] elements) {
    	int n = elements.length;
        int[] arr = new int[n * 2];
        for (int i = 0; i < n * 2; i++) { // 원형 전개
        	arr[i] = elements[i % n];
        }
        
        Set<Integer> set = new HashSet<>(); // 자동으로 중복을 제거할 HashSet
        
        for (int len = 1; len <= n; len++) {
        	int sum = 0;
            for (int i = 0; i < len; i++) sum += arr[i];
            set.add(sum);
            
            for (int start = 1; start < n; start++) {
            	sum = sum - arr[start - 1] + arr[start + len - 1];
                set.add(sum);
            } 
        }
        return set.size();
    }
}

문제 풀이 후기

원형 배열을 전개해서 인덱스 값 계산을 편리하게 하는 기법인 원형 전개와
연속된 구간을 한 칸씩 옮겨가며 계산하는 슬라이딩 윈도우에 대해 알 수 있었다.

틀린 문제를 복습 하면서 이전에는 풀지 못했던 문제를 스스로 다시 해결해가는
과정을 통해 체감은 못하고 있었지만 그래도 성장했다는 것을 느낄 수 있었다.