연속 부분 수열 합의 개수

문제

철호는 원형 수열의 모든 연속 부분 수열에 대한 합을 구하고, 이 합들로 만들 수 있는 서로 다른 수의 개수를 구하려고 합니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 원형 수열의 모든 원소 elements가 주어질 때, 연속 부분 수열의 합으로 만들 수 있는 서로 다른 수의 개수를 반환하는 프로그램을 작성하는 문제입니다.

• 입력: 원형 수열의 원소가 담긴 정수 배열 elements (길이 3 이상 1,000 이하, 원소는 1 이상 1,000 이하의 자연수)
• 출력: 연속 부분 수열의 합으로 만들 수 있는 고유한 수의 개수

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

풀이 1: 원형 수열의 선형 전개

원형 수열 문제를 풀 때 가장 널리 쓰이고 직관적인 기법인 '배열을 두 배로 늘려 일자로 펼치는 것'입니다. 배열을 복사해 이어 붙이면 일반적인 선형 배열처럼 탐색할 수 있습니다.

• 원형 수열 선형 전개: 주어진 elements 배열의 길이를 n이라고 할 때, 부분 수열의 최대 길이는 n입니다. 따라서 시작 인덱스가 배열의 마지막 원소일 때 최대 n개의 원소를 이어서 보려면 앞부분의 원소 n-1개가 뒤에 더 필요합니다. 빈 ArrayList에 원본 배열을 한 번 다 넣고, 이어서 n-1개만큼 한 번 더 넣어서 총 길이 2n - 1의 선형 리스트를 만들어 원형 수열을 모사합니다.
• 이중 반복문을 통한 구간 합 탐색:
  • 바깥쪽 반복문 (i): 부분 수열의 시작 인덱스.
  • 안쪽 반복문 (j): 시작점 i부터 1개씩 길이를 늘려가며 합을 누적(sum)하고 HashSet에 기록합니다.

코드 1

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        List<Integer> list = new ArrayList<>();
        int n = elements.length;
        
        // 원형 수열을 선형으로 펼치기 (원본 삽입 + n-1개 추가 삽입)
        for (int i = 0; i < n; i++) {
            list.add(elements[i]);
        }
        for (int i = 0; i < n - 1; i++) {
            list.add(elements[i]);
        }
        
        Set<Integer> set = new HashSet<>();
        
        // 시작점을 0부터 n-1까지 이동하며 모든 경우 탐색
        for (int i = 0; i <= list.size() - n; i++) {
            int sum = 0;
            // 시작점 i부터 길이 1~n까지 연속된 원소의 합 누적
            for (int j = 0; j < n; j++) {
                sum += list.get(i + j);
                set.add(sum);
            }
        }
        
        return set.size();
    }
}

풀이 2: 모듈러(%) 연산을 활용한 공간 최적화

풀이 1처럼 새로운 리스트나 배열을 만들지 않고, 원본 배열 하나만 유지한 채 인덱스에 모듈러(%) 연산을 적용하여 원형 큐처럼 순환시키는 최적화 풀이입니다.

• 모듈러 연산의 원리: 시작 인덱스 i에서 길이 j만큼 이동한 실제 인덱스는 i + j가 됩니다. 이때 배열의 길이 n을 넘어가는 것을 방지하기 위해 (i + j) % n을 적용하면, 배열의 끝을 넘어서는 순간 다시 0번 인덱스부터 순환하여 접근하게 됩니다.
• 공간 복잡도 단축: 새로운 ArrayList를 할당하고 값을 복사하는 메모리 공간과 오버헤드를 0으로 줄여줍니다. 또한 배열 인덱싱 속도가 리스트의 get() 메서드보다 빠르므로 실행 시간도 더욱 단축됩니다.

코드 2

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();
        int n = elements.length;
        
        // i는 부분 수열의 시작 인덱스
        for (int i = 0; i < n; i++) {
            int sum = 0;
            
            // j는 더해나갈 원소의 개수 (길이 1부터 n까지)
            for (int j = 0; j < n; j++) {
                // 모듈러 연산으로 인덱스 초과 방지 및 순환 탐색
                sum += elements[(i + j) % n];
                set.add(sum);
            }
        }
        
        return set.size();
    }
}

풀이 3: 누적 합(Prefix Sum)과 여집합을 활용한 최적화

원형으로 이어지는 부분 수열은 "전체 합에서 중간의 일반적인 연속 구간을 잘라내고 남은 나머지(여집합)"와 같습니다. 이를 누적 합 배열과 결합하면 덧셈 반복 연산조차 제거할 수 있습니다.

• 누적 합과 전체 합: O(N)으로 누적 합 배열(psum)과 원소들의 총합(totalSum)을 미리 구합니다.
• 여집합(나머지 구간) 탐색: i부터 j까지의 일반적인 구간 합(partSum = psum[j + 1] - psum[i])을 구하여 Set에 넣습니다. 동시에, 전체 합에서 이를 뺀 값(totalSum - partSum)을 Set에 넣으면, 이것이 바로 원형으로 바깥쪽을 감싸는 부분 수열의 합이 됩니다.
• 효율성: 반복문 안에서 1칸씩 늘려가며 더하던 과정이 단순히 O(1) 뺄셈 2번으로 대체되므로 실행 속도가 가장 빠릅니다.

코드 3

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int n = elements.length;
        int[] psum = new int[n + 1];
        int totalSum = 0;
        
        // 1. 누적 합(Prefix Sum)과 전체 합 미리 계산
        for (int i = 0; i < n; i++) {
            totalSum += elements[i];
            psum[i + 1] = psum[i] + elements[i];
        }
        
        Set<Integer> set = new HashSet<>();
        // 전체 길이의 수열 합은 무조건 포함
        set.add(totalSum);
        
        // 2. 일반 구간 [i, j] 탐색
        for (int i = 0; i < n; i++) {
            // j를 n-1 미만으로 제한하여 빈 구간(합이 0) 발생 방지
            for (int j = i; j < n - 1; j++) { 
                
                // 1) 배열을 벗어나지 않는 일반 구간의 합
                int partSum = psum[j + 1] - psum[i];
                set.add(partSum);
                
                // 2) 원형으로 이어지는 나머지 구간의 합 (여집합)
                set.add(totalSum - partSum);
            }
        }
        
        return set.size();
    }
}

알고리즘 분류

자료 구조 (Data Structures), 해시를 사용한 집합 (Hash Set), 슬라이딩 윈도우 (Sliding Window), 누적 합 (Prefix Sum), 모듈러 연산 (Modular Arithmetic)