[프로그래머스] 연속된 부분 수열의 합 - Java

• 프로그래머스 연속 수열 문제 링크

---

문제 요약

주어진 배열에서 연속된 부분 수열의 합이 k가 되는 구간을 찾고,
그 중 길이가 가장 짧은 구간의 시작, 끝 인덱스를 반환하는 문제다.

즉,

• 여러 개의 답이 있을 수 있으므로,
• 길이가 가장 짧은 것을 우선하고, 그 중 가장 앞쪽에 위치한 것을 반환한다.

---

핵심 아이디어

이 문제는 고정 길이가 아닌 가변 길이 윈도우를 다루므로,
두 포인터로 윈도우를 동적으로 조절한다.

핵심 로직:
1. sum == k → 길이 기록 후 윈도우 왼쪽 축소 (더 짧은 구간 탐색)
2. sum > k → 윈도우 왼쪽 축소 (합 줄이기)
3. sum < k → 윈도우 오른쪽 확장 (합 늘리기)

---

알고리즘 핵심 로직

start = 0, end = 0, sum = 0
while end < n:
    if sum == k:
        길이 기록 후 start++
        sum -= sequence[start]
    elif sum > k:
        start++
        sum -= sequence[start]
    elif sum < k:
        end++
        sum += sequence[end]

핵심:

• 모든 가능한 구간을 탐색하면서 최소 길이를 추적
• 길이가 같으면 가장 앞쪽 (작은 start 우선)

---

전체 코드 (제출용)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int startIdx = 0;
        int endIdx = 0;
        int sum = sequence[startIdx];

        List<int[]> list = new ArrayList<>();

        while (startIdx <= endIdx && endIdx < sequence.length) {
            if (sum == k) {
                list.add(new int[]{startIdx, endIdx});
                sum -= sequence[startIdx];
                startIdx++;
            } else if (sum > k) {
                sum -= sequence[startIdx];
                startIdx++;
                if (startIdx > endIdx) {
                    endIdx++;
                    if (sequence.length == endIdx) break;
                    sum += sequence[endIdx];
                }
            } else if (sum < k) {
                endIdx++;
                if (sequence.length == endIdx) break;
                sum += sequence[endIdx];
            }
        }

        int[] answer = new int[2];
        int arrMinLength = Integer.MAX_VALUE;

        for (int[] a : list) {
            int arrLength = a[1] - a[0] + 1;
            if (arrMinLength > arrLength) {
                arrMinLength = arrLength;
                answer = a;
            }
        }
        
        return answer;
    }
}

---

예제 시뮬레이션

입력: sequence = [1, 2, 1, 3, 0, 5, 9, 2], k = 7

구간	start	end	합	길이	선택
[0:6]	0	6	1+2+1+3+0+5+9=21	7	-
축소	1	6	2+1+3+0+5+9=20	6	-
...	...	...	...	...	...
[5:6]	5	6	5+9=14	2	-
[6:6]	6	6	9 > 7	-	-
[2:4]	2	4	1+3+0=4	3	후보
[3:5]	3	5	3+0+5=8	3	후보
[5:6]	5	6	5+9=14	2	최소 길이

결과: [5, 6] (길이 2)

---

핵심 포인트 정리

• 가변 길이 슬라이딩 윈도우의 대표 예제
• sum == k 발견 시 왼쪽 축소로 더 짧은 구간 탐색
• 여러 답 존재 시 최소 길이 우선, 그중 앞쪽 우선
• 시간 복잡도: (O(n))