[프로그래머스] 연속된 부분 수열의 합 (Java) - 투 포인터

📌 핵심 요약

• 투 포인터로 O(N) 풀이 — 수열 길이가 최대 100만이라 O(N²) 완전 탐색은 시간 초과. left/right 두 포인터로 윈도우를 늘렸다 줄였다 하며 한 번만 훑습니다.
• 성립 근거는 단조성 — 모든 원소가 1 이상(양수)이라 right를 밀면 합이 반드시 커지고 left를 밀면 반드시 작아집니다. 이 성질 덕분에 각 상황에서 취할 행동이 하나로 정해집니다.
• 동점 처리는 부등호 하나로 — "길이가 같으면 시작 인덱스가 작은 것" 조건은 탐색 방향(왼쪽→오른쪽)과 엄격한 부등호(<)의 조합으로 자연스럽게 해결됩니다.

 

 

목차

1 문제 소개

Programmers #178870

연속된 부분 수열의 합

수열 길이 ≤ 1,000,000 · 원소 1~1,000 · k ≤ 10억

난이도: Programmers Lv.2

비내림차순으로 정렬된 수열 sequence와 정수 k가 주어질 때, 원소의 합이 k인 연속된 부분 수열을 찾아 [시작 인덱스, 끝 인덱스]를 반환하는 문제입니다. 조건을 만족하는 수열이 여러 개라면 길이가 가장 짧은 것, 길이도 같다면 시작 인덱스가 가장 작은 것을 골라야 합니다. (합이 k인 부분 수열은 항상 존재한다고 보장됩니다.)

예를 들어 sequence = [1, 2, 3, 4, 5], k = 7이면 합이 7인 구간은 [3, 4](인덱스 2~3) 하나뿐이므로 답은 [2, 3]입니다. sequence = [2, 2, 2, 2, 2], k = 6이면 합이 6인 구간이 세 개인데 길이가 모두 3으로 같으므로, 시작 인덱스가 가장 작은 [0, 2]가 답입니다.

2 접근 방법

제한 조건에서 출발하기

가장 먼저 확인한 것은 수열의 길이입니다.

최대 100만이므로, 모든 시작/끝 인덱스 쌍을 시도하는 O(N²) 완전 탐색은 최악의 경우 약 5,000억 번 연산이 되어 시간 초과를 피할 수 없습니다. O(N) 또는 O(N log N) 수준의 풀이가 필요합니다.

다음으로 눈에 들어온 것은 원소가 전부 1 이상의 양수라는 조건입니다.

이 조건이 왜 중요하냐면, 구간의 오른쪽 끝을 늘리면 합이 반드시 증가하고 왼쪽 끝을 줄이면 반드시 감소하는 단조성이 보장되기 때문입니다.

이 단조성이 성립하면 투 포인터(가변 크기 윈도우)를 쓸 수 있습니다.

투 포인터의 동작

left와 right 두 포인터로 구간 [left, right]를 관리하면서, 매 순간 합과 k를 비교해 행동을 결정합니다.

• 합이 k보다 작으면 → right를 오른쪽으로 밀어 구간을 늘린다 (합 증가)
• 합이 k보다 크면 → left를 오른쪽으로 밀어 구간을 줄인다 (합 감소)
• 합이 k와 같으면 → 정답 후보로 기록한다

단조성 덕분에 각 상황에서 취할 행동이 하나로 정해지고, 두 포인터 모두 뒤로 돌아가는 일 없이 각자 최대 N번만 전진하므로 전체 시간 복잡도는 O(N)입니다.

⚠️

0이나 음수가 섞여 있었다면?

구간을 늘렸는데 합이 그대로거나 오히려 줄어드는 상황이 생겨 단조성이 깨지고, 투 포인터로는 놓치는 구간이 발생합니다. 이 문제는 원소가 전부 양수라서 가능한 풀이라는 점을 유의해야합니다.

3 Java 코드

   

Java — Solution.java (투 포인터, O(N))

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        long total = 0;                       // 현재 구간의 합
        int left = 0;                        // 구간의 왼쪽 끝
        int minLength = Integer.MAX_VALUE;   // 지금까지 찾은 최소 길이

        for (int right = 0; right < sequence.length; right++) {
            // 1. 오른쪽 끝을 한 칸 확장
            total += sequence[right];

            // 2. 합이 k를 초과하면 왼쪽 끝을 밀어서 구간을 줄인다
            while (total > k) {
                total -= sequence[left];
                left++;
            }

            // 3. 합이 정확히 k인 구간 발견 → 더 짧을 때만 갱신
            if (total == k) {
                int currentLength = right - left + 1;
                if (currentLength < minLength) {
                    minLength = currentLength;
                    answer[0] = left;
                    answer[1] = right;
                }
            }
        }

        return answer;
    }
}

4 놓치기 쉬운 포인트

💡

동점 처리는 부등호 하나로 끝난다

right가 왼쪽에서 오른쪽으로 진행하므로, 같은 길이의 구간이라면 시작 인덱스가 작은 쪽이 항상 먼저 발견됩니다. 갱신 조건을 currentLength < minLength처럼 등호 없는 엄격한 부등호로 두면, 나중에 나온 같은 길이 구간이 앞의 답을 덮어쓰지 못합니다. 만약 <=로 썼다면 뒤쪽 구간으로 덮어써서 오답이 됩니다.

⚠️

"total == k일 때 left를 더 안 밀어도 되나?"

저도 처음에 잠깐 헷갈렸던 부분인데, 원소가 전부 양수라서 total == k인 상태에서 left를 밀면 합이 무조건 k 미만으로 떨어집니다. 즉 현재 right에서 합이 k가 되는 구간은 지금 그 하나뿐이므로 추가 탐색이 필요 없습니다.

ℹ️

누적 합 변수는 범위 계산부터

while문 덕분에 매 반복이 끝나면 total ≤ k가 보장되고, 다음 원소를 더해도 최대 k + 1,000 ≈ 10억 + 1,000이라 사실 int 범위(약 21.4억) 안입니다. 다만 k가 조금만 더 컸다면 오버플로가 나는 아슬아슬한 코드였습니다. 누적 합 변수는 일단 최대값부터 계산해 보고, 애매하면 long을 쓰는 습관을 들이는 것이 안전합니다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.