투 포인터(Two Pointer) with Kotlin

투 포인터(Two Pointer)

투 포인터(Two Pointer) 알고리즘은 배열이나 리스트에서 두 개의 점을 이동시키면서 원하는 결과를 얻어내는 알고리즘이다. 예를 들어 부분합을 구하는 문제에서 배열과 부분합을 구할 특정 인덱스가 주어지는 것이 아니라 특정 값이 주어지고 부분합이 주어진 값과 일치하는 구간의 수 또는 구간의 최대/최소 길이를 구해야 하는 경우를 생각해볼 수 있다. 이 경우에 누적합이 계산된 배열이 있어도 단순히 이중 반복문으로 답을 찾게 되면 \(O(n^{2})\)의 시간 복잡도를 갖게 되어 배열의 크기가 10만 정도만 되더라도 100억회의 연산을 해야하기 때문에 굉장히 비효율적이다.

 

이럴 때 투 포인터를 사용하는 것이 대안이 될 수 있다. 투 포인터는 각각 구간의 시작과 끝을 가리키는 start와 end를 선언하고 배열의 시작점부터 조건에 따라 이동하면서 구간을 형성한다. 아래의 예제는 주어진 배열에서 구간의 합이 5 이상인 구간의 개수를 구하는 문제를 나타낸 것이다.

이 예제를 코드로 작성하면 다음과 같다. 코드 작성의 편의 상 배열의 첫 요소 앞에 0을 놓고 계산한다.

fun check(arr: IntArray): Int {
    val prefixSum = IntArray(arr.size)
    for (i in 1..arr.lastIndex) {
        prefixSum[i] = prefixSum[i - 1] + arr[i]
    }
    var start = 1
    var end = 1
    var count = 0
    while (end <= prefixSum.lastIndex) {
        if (prefixSum[end] - prefixSum[start - 1] >= 5) {
            count++
            start++
        } else {
            end++
        }

        if (start > end) end++
    }

    return count
}

우선 구간의 합을 수월하게 계산하기 위한 누적합 배열을 생성한다. 이후 구간의 합에 따라 다음과 같이 포인터를 이동시킨다.

• 부분합이 5 이상인 경우 : 구간의 개수를 1 증가시키고 start가 오른쪽으로 한칸 이동한다.
• 부분합이 5 미만인 경우 : end가 오른쪽으로 한칸 이동한다.

이 때 start가 end보다 오른쪽에 올 수는 없으므로 start가 end를 넘어가면 end도 같이 이동시킨다. 이 과정을 end가 배열의 크기를 넘어가기 전까지 반복한다. 이 경우의 시간 복잡도는 두 포인터 중 하나는 반드시 1씩 증가하고, 각 포인터가 배열의 끝에 도달해야 끝나기 때문에 \(O(2n)=O(n)\)이 된다.