programmers) 연속된 부분 수열의 합 | 두 번째 풀이

연속된 부분 수열의 합 | 두 번째 풀이

3주 전에 풀었던 프로그래머스 연속된 부분 수열의 합 문제를 다시 풀어봤다.

이전에 풀었던 기록은 아래 글에 정리해두었다.

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

이전에 풀었을 때도 투 포인터를 사용했지만, 그때는 for문 + while문 구조로 풀었다.
이번에는 while문 하나를 사용해서 left와 right를 직접 움직이는 방식으로 다시 풀어봤다.

---

문제 이해하기

이 문제는 주어진 수열 sequence에서 합이 k가 되는 연속된 부분 수열을 찾는 문제다.

조건은 다음과 같다.

1. 연속된 구간의 합이 k가 되어야 한다.
2. 합이 k인 구간이 여러 개라면 길이가 가장 짧은 구간을 선택한다.
3. 길이가 같다면 시작 인덱스가 더 작은 구간을 선택한다.

예를 들어,

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

이라면 합이 7이 되는 연속 구간은 [3, 4]이다.

인덱스로 보면 2부터 3까지이므로 정답은 다음과 같다.

[2, 3]

---

이전 풀이와 이번 풀이의 차이

이전에 풀었을 때는 for문으로 right를 하나씩 증가시키고, 합이 k보다 커졌을 때 while문으로 left를 움직이는 방식이었다.

대략 이런 느낌이다.

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) {
        // 정답 후보 저장
    }
}

이 방식에서는 right가 for문에 의해 자동으로 증가한다.
그리고 left는 합이 커졌을 때만 while문 안에서 움직인다.

이번 풀이에서는 while문 하나 안에서 현재 합의 상태를 보고 left 또는 right를 직접 움직였다.

sum < k  → right 증가
sum > k  → left 증가
sum == k → 정답 후보 저장 후 left 증가

둘 다 투 포인터 풀이지만, 이번 풀이가 포인터의 움직임을 더 직접적으로 볼 수 있어서 좋았다.

---

투 포인터로 접근한 이유

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

단순하게 생각하면 시작점을 하나씩 정하고, 끝점을 늘려가며 모든 구간의 합을 확인할 수도 있다.
하지만 그렇게 하면 확인해야 하는 구간이 많아져서 비효율적이다.

이 문제는 수열이 비내림차순이라는 특징이 있다.
그래서 현재 구간의 합이 작으면 오른쪽으로 구간을 넓히고, 합이 크면 왼쪽을 줄이는 방식이 가능하다.

즉, 현재 합을 기준으로 구간을 조절할 수 있기 때문에 투 포인터를 사용할 수 있다.

---

핵심 아이디어

left는 현재 구간의 시작 인덱스,
right는 현재 구간의 끝 인덱스로 두었다.

처음에는 [0, 0] 구간에서 시작한다.

int left = 0;
int right = 0;
int sum = sequence[0];

현재 구간은 sequence[left]부터 sequence[right]까지다.

예를 들어 아래 배열이 있다면,

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

현재 구간은 [1]이고, 합은 1이다.

여기서 합이 k보다 작으면 오른쪽을 늘린다.

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

반대로 합이 k보다 크면 왼쪽 값을 빼고 left를 이동한다.

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

이렇게 현재 합에 따라 구간을 넓히거나 줄이면서 답을 찾는다.

---

처음에 헷갈렸던 부분

처음에는 반복문 안에서 계속 sum += sequence[right]를 해주려고 했다.

sum += sequence[right];

그런데 이렇게 하면 right가 움직이지 않았는데도 같은 값을 또 더할 수 있다.

투 포인터에서는 sum을 매번 새로 계산하는 것이 아니라, 포인터가 움직일 때만 합을 갱신해야 한다.

정리하면 다음과 같다.

right가 움직이면 새로 포함된 값을 sum에 더한다.
left가 움직이면 빠지는 값을 sum에서 뺀다.

이 부분을 이해하고 나니 코드 흐름이 훨씬 깔끔해졌다.

---

풀이 흐름

현재 합이 k와 같은 경우에는 정답 후보가 된다.

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

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

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

정답을 찾았다고 바로 멈추면 안 된다.
뒤쪽에 더 짧은 구간이 나올 수 있기 때문이다.

그래서 정답 후보를 저장한 뒤, 왼쪽 값을 빼고 다음 구간을 확인한다.

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

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

현재 합이 k보다 작으면 오른쪽으로 구간을 넓힌다.

else {
    right++;

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

여기서 right가 배열 범위를 벗어나지 않도록 조건을 확인해주었다.

---

길이가 같은 경우 조건

문제 조건에는 길이가 같다면 시작 인덱스가 작은 구간을 선택하라고 되어 있다.

그래서 조건을 명확하게 코드로 표현하면 이렇게 쓸 수 있다.

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

이 조건의 의미는 다음과 같다.

현재 구간이 더 짧으면 정답 갱신
또는
길이가 같고 시작 인덱스가 더 작으면 정답 갱신

사실 이 문제에서는 투 포인터가 앞에서부터 탐색되기 때문에, 같은 길이의 구간이 나중에 나온다면 시작 인덱스는 더 뒤에 있다.
그래서 실제로는 아래처럼 더 짧은 경우에만 갱신해도 통과할 수 있다.

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

하지만 문제 조건을 코드에 더 명확하게 드러내고 싶다면, 길이가 같은 경우까지 포함한 조건문을 작성하는 것도 괜찮다고 생각했다.

---

최종 코드

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

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

        while (left < sequence.length && right < sequence.length) {
            if (sum == k) {
                int length = right - left + 1;

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

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

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

            } else {
                right++;

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

        return answer;
    }
}

---

시간 복잡도

left와 right는 각각 배열의 끝까지 한 번씩만 이동한다.

그래서 시간 복잡도는 다음과 같다.

O(n)

추가로 사용하는 변수도 많지 않기 때문에 공간 복잡도는 다음과 같다.

O(1)

---

정리

이번 문제는 예전에 풀었던 문제를 약 3주 만에 다시 풀어본 거라서 더 의미가 있었다.

처음 풀었을 때는 for문 + while문으로 투 포인터를 구현했다.
이번에는 while문 하나로 현재 합에 따라 left와 right를 직접 움직이는 방식으로 풀었다.

둘 다 투 포인터 풀이지만, 이번 방식은 포인터가 왜 움직이는지 더 잘 보였다.

중요한 핵심은 이것이다.

합이 작으면 right 증가
합이 크면 left 증가
합이 같으면 정답 저장 후 left 증가

그리고 sum은 반복문마다 무조건 더하는 것이 아니라, 포인터가 움직일 때만 더하거나 빼야 한다.

같은 문제를 다시 풀어보니, 예전에는 그냥 코드 흐름을 따라가며 풀었다면 이번에는 투 포인터가 움직이는 이유를 조금 더 이해하게 된 것 같다.