programmers) 연속된 부분 수열의 합

연속된 부분 수열의 합 Java 풀이 — 투포인터로 시간초과 해결하기

1. 문제 소개

이번에 풀어본 문제는 프로그래머스 Lv.2 문제인 연속된 부분 수열의 합이다.

문제에서는 비내림차순으로 정렬된 정수 배열 sequence와 정수 k가 주어진다.
이때 합이 k가 되는 연속된 부분 수열을 찾아, 해당 구간의 시작 인덱스와 마지막 인덱스를 배열로 반환해야 한다.

조건은 다음과 같다.

• 부분 수열의 합은 k여야 한다.
• 합이 k인 부분 수열이 여러 개라면 길이가 가장 짧은 수열을 선택한다.
• 길이도 같다면 시작 인덱스가 더 작은 수열을 선택한다.

처음에는 단순히 모든 구간의 합을 구하면 되지 않을까 생각했다.
하지만 제한사항을 보고 완전탐색으로는 풀기 어렵다는 것을 알 수 있었다.

---

2. 제한사항 확인

문제의 제한사항은 다음과 같다.

5 ≤ sequence의 길이 ≤ 1,000,000
1 ≤ sequence의 원소 ≤ 1,000
sequence는 비내림차순으로 정렬되어 있습니다.
5 ≤ k ≤ 1,000,000,000
k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

여기서 가장 중요하게 봐야 할 조건은 두 가지다.

sequence의 길이는 최대 1,000,000
sequence의 원소는 모두 양수

배열의 길이가 최대 1,000,000이기 때문에 이중 반복문으로 모든 구간을 확인하면 시간초과가 발생할 가능성이 높다.

예를 들어 모든 시작 인덱스와 끝 인덱스를 확인하는 방식은 최악의 경우 O(N²)이 된다.

for (int i = 0; i < sequence.length; i++) {
    int sum = 0;

    for (int j = i; j < sequence.length; j++) {
        sum += sequence[j];

        if (sum == k) {
            // 정답 후보
        }
    }
}

N이 1,000,000이면 O(N²) 방식은 사실상 사용할 수 없다.
따라서 이 문제는 O(N)에 가까운 방식으로 풀어야 한다.

---

3. 비내림차순이란?

문제 설명에 sequence는 비내림차순으로 정렬되어 있다고 되어 있다.

비내림차순이란 쉽게 말해 값이 작아지지 않는 순서를 뜻한다.

a1 <= a2 <= a3 <= ... <= an

즉, 뒤로 갈수록 값이 커지거나 같을 수는 있지만, 작아지면 안 된다.

예를 들어 아래 배열은 비내림차순이다.

[1, 2, 2, 3, 5]
[1, 1, 1, 1]
[2, 3, 3, 4, 4, 5]

반대로 아래 배열은 비내림차순이 아니다.

[1, 3, 2, 4]
[5, 4, 4, 3]

중요한 점은 비내림차순은 중복 값을 포함할 수 있는 정렬이라는 것이다.

일반적으로 오름차순이라고 하면 값이 점점 커지는 순서를 떠올리지만, 코딩테스트에서 말하는 비내림차순은 1, 2, 2, 3처럼 같은 값이 여러 번 나와도 괜찮다.

정리하면 다음과 같다.

용어	의미	예시
오름차순	값이 점점 커지는 순서	[1, 2, 3, 4]
비내림차순	값이 작아지지 않는 순서, 중복 허용	[1, 2, 2, 3]
내림차순	값이 점점 작아지는 순서	[5, 4, 3, 2]
비오름차순	값이 커지지 않는 순서, 중복 허용	[5, 5, 4, 3]

---

4. 투포인터를 떠올린 이유

이 문제는 연속된 구간의 합을 구하는 문제다.

연속 구간 문제에서는 현재 구간의 합을 매번 새로 계산하지 않고, 기존 합에서 값을 더하거나 빼면서 관리할 수 있다.

이때 사용할 수 있는 대표적인 방법이 투포인터다.

투포인터에서는 보통 두 개의 인덱스를 사용한다.

left  : 현재 구간의 시작 인덱스
right : 현재 구간의 끝 인덱스
sum   : left부터 right까지의 합

이 문제에서는 원소가 모두 양수다.

따라서 다음이 성립한다.

right를 오른쪽으로 이동하면 sum이 증가한다.
left를 오른쪽으로 이동하면 sum이 감소한다.

그래서 현재 합에 따라 다음과 같이 판단할 수 있다.

sum < k  → 구간 합을 키워야 하므로 right 이동
sum > k  → 구간 합을 줄여야 하므로 left 이동
sum == k → 정답 후보 확인

이처럼 포인터를 한 방향으로만 이동시키면서 정답을 찾을 수 있기 때문에 전체 시간복잡도를 O(N)으로 줄일 수 있다.

---

5. 처음 작성하면서 헷갈렸던 부분

처음에는 left, right, sum을 사용하는 방향은 떠올렸지만, 몇 가지 실수가 있었다.

5-1. 정답 배열 초기화 실수

처음에는 아래처럼 작성했다.

int[] answer = {};

하지만 이 코드는 길이가 0인 배열을 만든다.

따라서 아래처럼 접근하면 오류가 발생한다.

answer[0] = left;
answer[1] = right;

answer 배열에는 0번, 1번 인덱스가 없기 때문이다.

그래서 정답 배열은 아래처럼 길이 2로 만들어야 한다.

int[] answer = {0, 0};

또는 이렇게 작성해도 된다.

int[] answer = new int[2];

둘 다 길이가 2인 int 배열을 만드는 방식이다.
int 배열의 기본값은 0이므로 이 문제에서는 두 방식 모두 사용할 수 있다.

---

5-2. =+, =- 실수

처음에 합을 더하고 뺄 때 아래처럼 쓰기 쉽다.

sum =+ sequence[right];
sum =- sequence[left];

하지만 이 코드는 의도한 코드가 아니다.

sum =+ sequence[right]는 sum += sequence[right]가 아니다.
기존 sum에 더하는 것이 아니라, sequence[right]의 양수 값을 sum에 대입하는 것처럼 동작한다.

올바른 코드는 다음과 같다.

sum += sequence[right];
sum -= sequence[left];

코딩테스트를 풀 때 이런 작은 문법 실수 때문에 런타임 오류나 오답이 발생할 수 있으므로 주의해야 한다.

---

6. 최종 풀이 코드

최종적으로 작성한 Java 코드는 다음과 같다.

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0, 0};

        int left = 0;
        int right = 0;
        int sum = 0;

        int minLength = Integer.MAX_VALUE;

        while (right < sequence.length) {
            sum += sequence[right];

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

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

                if (length < minLength) {
                    minLength = length;
                    answer[0] = left;
                    answer[1] = right;
                }
            }

            right++;
        }

        return answer;
    }
}

---

7. 코드 흐름 설명

먼저 정답 배열을 선언한다.

int[] answer = {0, 0};

이 문제에서는 k를 만들 수 있는 부분 수열이 항상 존재한다고 했기 때문에, 정답이 끝까지 갱신되지 않는 경우는 없다. 따라서 {0, 0}으로 초기화해도 괜찮다.

다음으로 포인터와 합을 초기화한다.

int left = 0;
int right = 0;
int sum = 0;

left는 현재 구간의 시작 인덱스이고, right는 현재 구간의 끝 인덱스다.
sum은 현재 구간의 합을 저장한다.

가장 짧은 구간을 찾아야 하므로 최소 길이를 저장할 변수도 필요하다.

int minLength = Integer.MAX_VALUE;

아직 정답 후보를 찾기 전이므로 가장 큰 값으로 초기화한다.

---

8. right로 구간 확장하기

반복문은 right가 배열 끝에 도달할 때까지 실행한다.

while (right < sequence.length) {
    sum += sequence[right];

현재 right 위치의 값을 sum에 더한다.
즉, 오른쪽으로 구간을 확장하는 것이다.

예를 들어 다음과 같은 배열이 있다고 하자.

sequence = [1, 2, 3, 4, 5]
k = 7

초기 상태는 다음과 같다.

left = 0
right = 0
sum = 0

right를 이동하면서 합을 더하면 다음과 같이 된다.

right = 0 → sum = 1
right = 1 → sum = 3
right = 2 → sum = 6
right = 3 → sum = 10

이때 sum이 k보다 커졌다.

---

9. left로 구간 줄이기

sum이 k보다 크면 구간 합을 줄여야 한다.

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

현재 구간의 왼쪽 값을 빼고, left를 오른쪽으로 이동한다.

위 예시에서 sum = 10이고 k = 7이라면 다음과 같이 동작한다.

sum = 10 - sequence[0]
sum = 10 - 1 = 9
left = 1

아직도 sum > k이므로 한 번 더 줄인다.

sum = 9 - sequence[1]
sum = 9 - 2 = 7
left = 2

이제 sum == k가 되었다.

현재 구간은 다음과 같다.

left = 2
right = 3
sequence[2] + sequence[3] = 3 + 4 = 7

따라서 [2, 3]은 정답 후보가 된다.

---

10. 정답 후보 갱신하기

현재 합이 k라면 정답 후보가 된다.

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

    if (length < minLength) {
        minLength = length;
        answer[0] = left;
        answer[1] = right;
    }
}

여기서 구간 길이는 다음과 같이 계산한다.

int length = right - left + 1;

기존에 찾은 구간보다 더 짧다면 정답을 갱신한다.

이 문제에서는 길이가 같을 경우 시작 인덱스가 더 작은 구간을 선택해야 한다.
그런데 위 코드에서는 length == minLength인 경우에는 갱신하지 않는다.

그 이유는 right가 왼쪽에서 오른쪽으로 순서대로 이동하기 때문이다.
같은 길이의 구간이 나중에 발견된다면 시작 인덱스도 더 뒤쪽일 가능성이 높다.

따라서 먼저 발견한 같은 길이의 구간을 유지하면 된다.

더 명시적으로 작성하고 싶다면 아래처럼 조건을 쓸 수도 있다.

if (length < minLength || (length == minLength && left < answer[0])) {
    minLength = length;
    answer[0] = left;
    answer[1] = right;
}

하지만 이 문제에서는 length < minLength만으로도 충분하다.

---

11. 시간복잡도 분석

이 풀이의 시간복잡도는 O(N)이다.

코드를 보면 while문 안에 또 다른 while문이 있어 O(N²)처럼 보일 수 있다.

while (right < sequence.length) {
    ...
    while (sum > k) {
        ...
    }
}

하지만 실제로는 그렇지 않다.

right는 배열의 처음부터 끝까지 한 번만 이동한다.

right: 0 → 1 → 2 → ... → n - 1

left도 마찬가지로 오른쪽으로만 이동한다.

left: 0 → 1 → 2 → ... → n - 1

즉, 각 포인터는 최대 N번씩만 이동한다.

따라서 전체 시간복잡도는 다음과 같다.

O(N)

공간복잡도는 추가 배열을 사용하지 않고 변수 몇 개만 사용하므로 O(1)이다.

---

12. 입력 크기가 더 컸다면?

문제에서는 sequence의 길이가 최대 1,000,000이다.
만약 입력 크기가 이보다 더 컸어도, 알고리즘 관점에서는 투포인터 풀이가 여전히 적합하다.

투포인터는 각 포인터가 배열을 한 번씩만 지나가기 때문에 O(N)에 해결할 수 있다.

다만 입력 크기가 훨씬 커진다면 고려해야 할 부분이 있다.

바로 sum의 자료형이다.

현재 문제의 제한에서는 최대 합이 다음과 같다.

sequence 길이 최대 1,000,000
sequence 원소 최대 1,000

최대 합 = 1,000,000 × 1,000 = 1,000,000,000

int의 최대값은 약 21억이다.

2,147,483,647

따라서 현재 문제에서는 int sum을 사용해도 범위 안에 들어온다.

하지만 만약 입력 크기가 더 커진다면 전체 합이 int 범위를 초과할 수 있다.

예를 들어 길이가 10,000,000이라면 다음과 같다.

10,000,000 × 1,000 = 10,000,000,000

이 값은 int 범위를 넘는다.

그래서 더 큰 입력을 고려한다면 sum은 long으로 선언하는 것이 안전하다.

long sum = 0;

안전하게 작성하면 다음과 같다.

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0, 0};

        int left = 0;
        long sum = 0;

        int minLength = 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 length = right - left + 1;

                if (length < minLength) {
                    minLength = length;
                    answer[0] = left;
                    answer[1] = right;
                }
            }
        }

        return answer;
    }
}

현재 프로그래머스 문제에서는 int로도 통과 가능하지만, 더 큰 입력을 고려하는 습관을 들이려면 long을 사용하는 것도 좋다.

---

13. 다른 접근 방법과 비교

이 문제는 누적합으로도 풀 수 있다.

예를 들어 prefix[i]를 sequence[0]부터 sequence[i - 1]까지의 합이라고 정의하면, 구간 [left, right]의 합은 다음과 같이 구할 수 있다.

prefix[right + 1] - prefix[left]

이 방식으로 prefix[left] + k가 되는 값을 이분탐색으로 찾는 풀이도 가능하다.

하지만 이 경우 시간복잡도는 보통 O(N log N)이 된다.
투포인터의 O(N)보다 비효율적이다.

또한 누적합 배열을 별도로 만들어야 하므로 공간복잡도도 O(N)이 된다.

반면 투포인터 풀이는 다음과 같다.

시간복잡도: O(N)
공간복잡도: O(1)

따라서 이 문제에서는 투포인터가 가장 적합하다.

---

14. 최종 정리

이번 문제는 투포인터의 기본 개념을 익히기에 좋은 문제였다.

핵심은 다음과 같다.

right를 이동하면서 구간을 확장한다.
sum이 k보다 커지면 left를 이동하면서 구간을 줄인다.
sum이 k와 같으면 정답 후보로 기록한다.
기존 정답보다 더 짧은 구간이면 갱신한다.

최종적으로 기억할 템플릿은 아래와 같다.

int left = 0;
int sum = 0;

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

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

    if (sum == k) {
        // 정답 후보 처리
    }
}

이 문제를 풀면서 느낀 점은, 투포인터 문제에서는 단순히 left, right를 사용하는 것보다 각 포인터의 역할을 먼저 정의하는 것이 중요하다는 점이다.

이번 문제에서는 다음처럼 역할을 정리할 수 있었다.

right는 구간을 넓히는 역할
left는 구간을 줄이는 역할
sum은 현재 구간의 합을 저장하는 역할

또한 “비내림차순”은 중복 값을 포함할 수 있는 정렬이라는 점도 다시 정리할 수 있었다.

결론적으로 이 문제는 완전탐색으로 접근하면 시간초과가 발생하기 쉽지만, 투포인터를 사용하면 O(N)에 효율적으로 해결할 수 있는 문제였다.