연속된 부분 수열의 합

문제

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 연속된 부분 수열을 찾는 문제입니다.

1. 부분 수열의 합은 k입니다.
2. 합이 k인 부분 수열이 여러 개인 경우 길이가 가장 짧은 수열을 찾습니다.
3. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

• 입력: 오름차순으로 정렬된 정수 배열 sequence (길이 5 이상 1,000,000 이하), 부분 수열의 합 k
• 출력: 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 담은 배열

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

풀이: 투 포인터를 활용한 부분 합 탐색

배열의 길이가 최대 1,000,000이므로 이중 반복문으로 모든 구간의 합을 구하면 O(N^2)으로 시간 초과가 발생합니다. 하지만 수열이 '오름차순'으로 정렬되어 있고 모든 원소가 양수이므로, 두 개의 포인터(l, r)를 사용하여 O(N)의 시간 복잡도로 빠르게 구간의 합을 조절할 수 있습니다.

• 포인터 및 누적 합 초기화: 왼쪽 포인터 l과 오른쪽 포인터 r을 모두 0으로 시작합니다. 초기 누적 합 sum은 sequence[0]으로 설정합니다.
• 최단 길이 기록: 정답 배열 ans의 인덱스 차이가 곧 구간의 길이가 됩니다. 처음에는 어떤 길이보다도 크게 비교되도록 ans[1]에 배열의 최대 길이인 sequence.length를 넣어줍니다.
• 구간 합 조절 (Two Pointers): 오른쪽 포인터 r이 배열의 끝에 도달할 때까지 반복합니다.
  • sum <= k 인 경우 (구간 확장):
    • 현재 합이 k와 정확히 일치한다면, 현재 찾은 구간의 길이(r - l)가 기존에 저장된 최단 길이(ans[1] - ans[0])보다 엄격히 작은 경우에만 정답을 갱신합니다. 이렇게 하면 길이가 같을 때 시작 인덱스가 작은 것을 우선하는 조건이 자연스럽게 만족됩니다.
    • 이후 합을 더 키우기 위해 오른쪽 포인터 r을 1 증가시키고, 배열 범위를 벗어나지 않는다면 sum에 값을 더해줍니다.
  • sum > k 인 경우 (구간 축소):
    • 현재 합이 k를 초과했으므로, 합을 줄이기 위해 누적 합에서 sequence[l]의 값을 빼고 왼쪽 포인터 l을 1 증가시켜 구간을 좁힙니다.

코드

class Solution {
    public int[] solution(int[] sequence, int k) {        
        int l = 0, r = 0, sum = sequence[0];
        int[] ans = new int[2];
        
        // 최단 길이를 찾기 위해 초기 끝점을 배열의 최대 길이로 설정
        ans[1] = sequence.length;
        
        while (r < sequence.length) {
            // 1. 누적 합이 k 이하인 경우 (구간 유지 또는 확장)
            if (sum <= k) {
                // 정확히 k와 일치하고, 기존에 찾은 길이보다 짧은 경우 정답 갱신
                if (sum == k) {
                    if (ans[1] - ans[0] > r - l) {
                        ans[0] = l;
                        ans[1] = r;
                    }
                }
                
                // 오른쪽 포인터를 이동시켜 합을 키움
                r++;
                if (r != sequence.length) {
                    sum += sequence[r];
                }
            } 
            // 2. 누적 합이 k를 초과한 경우 (구간 축소)
            else {
                sum -= sequence[l];
                l++;
            }
        }
        
        return ans;      
    }
}

알고리즘 분류

투 포인터 (Two Pointers), 슬라이딩 윈도우 (Sliding Window)