[슬라이딩윈도우] 프로그래머스 - 연속된 부분 수열의 합 (JAVA)

1. 문제

연속된 부분 수열의 합 (프로그래머스 Lv.2)

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

기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.

부분 수열의 합은 k입니다.

합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.

길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 반환하면 됩니다. 인덱스는 0부터 시작합니다.
https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

제한사항

항목	범위
sequence의 길이	5 이상 1,000,000 이하
sequence의 원소	1 이상 1,000 이하
정렬 상태	비내림차순 정렬
k	5 이상 1,000,000,000 이하
정답 존재 여부	k는 항상 부분 수열로 만들 수 있는 값

입출력 예

sequence	k	result
[1, 2, 3, 4, 5]	7	[2, 3]
[1, 1, 1, 2, 3, 4, 5]	5	[6, 6]

두 번째 예시는 합이 5인 연속 부분 수열이 [1, 1, 1, 2], [2, 3], [5] 세 개인데, 길이가 가장 짧은 [5]가 정답이 되어 [6, 6]을 반환합니다.

2. 틀린 이유

처음 접근: 백트래킹

합이 k가 되는 구간을 전부 찾아서 그중 최소 길이를 고르면 되겠다라고 생각했습니다. 시작 인덱스를 하나 잡고 뒤로 하나씩 더해 나가다가 합이 k를 넘으면 방식이었습니다. 그러나 시간 초과가 발생했습니다.

틀린 이유

구간의 개수 자체가 너무 많습니다. 길이 N인 배열에서 연속 구간의 개수는 N(N+1)/2개입니다. N이 최대 1,000,000이므로 대략 5 곱하기 10의 11승, 즉 5,000억 개가 됩니다.

가지치기를 해도 구조가 O(N제곱)입니다. 합이 k를 넘으면 즉시 되돌아오는 가지치기를 넣어도, 시작 인덱스마다 다시 처음부터 더하기 시작하기 때문에 시작점 N개를 모두 훑는 비용은 사라지지 않습니다.

이미 계산한 합을 버리고 있었습니다. 시작 인덱스가 0일 때 구한 부분합과 1일 때 구한 부분합은 대부분이 겹치는데, 백트래킹 구조에서는 그 결과를 재사용하지 못하고 매번 새로 더했습니다.

문제를 다시 읽어 보니 sequence의 원소는 모두 1 이상의 자연수라는 제한이 있었습니다. 이 조건이 있으면 구간을 오른쪽으로 늘리면 합이 반드시 증가하고, 왼쪽을 줄이면 합이 반드시 감소합니다. 

3. 알고리즘 풀이과정

슬라이딩 윈도우란

배열 위에 크기가 변하는 창문을 두고, 왼쪽 끝(left)과 오른쪽 끝(right) 두 포인터를 한 방향으로만 밀면서 조건을 만족하는 구간을 찾는 기법입니다. 매번 구간의 합을 새로 계산하지 않고, 창문이 이동할 때 들어온 값은 더하고 나간 값은 빼는 방식으로 갱신합니다.

동작 순서

1단계. right를 0부터 끝까지 한 칸씩 옮기면서 sequence[right]를 sum에 더해 창문을 넓힙니다.

2단계. sum이 k보다 커지면 sequence[left]를 빼고 left를 증가시켜 창문을 왼쪽부터 줄입니다. sum이 k 이하가 될 때까지 반복해요.

3단계. sum이 정확히 k와 같아지면 현재 구간 길이를 계산해 지금까지의 최솟값과 비교합니다.

4단계. 더 짧으면 minLen과 정답 인덱스를 갱신하고, right를 계속 진행합니다.

4. 코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int left = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;

        for(int right = 0; right < sequence.length; right++) {
            sum += sequence[right];

            while(sum > k) {
                sum -= sequence[left];
                left++;
            }

            if(sum == k) {
                int len = right - left + 1;

                if(len < minLen) {
                    minLen = len;
                    answer[0] = left;
                    answer[1] = right;
                }
            }
        }
        return answer;
    }
}