[PS] 투 포인터

Hood·2024년 10월 20일

ps two pointer

PS

목록 보기

3/15

✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘

소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 Kotlin을 기반으로 작성하였습니다.

투 포인터

일반적인 배열에서는 연속된 값의 범위를 하나의 구간으로 표현할 수 있습니다.

투 포인터(Two Pointers) 알고리즘은 바로 이 구간의 개념을 활용하는 알고리즘입니다.

PS 문제를 풀다 보면 배열을 순회하면서 특정 조건을 만족하는 구간을 찾아야 하는 경우가 자주 있습니다.
이때 모든 구간을 직접 확인하면 연산 횟수가 너무 많아져 시간 초과가 발생할 수 있습니다.
즉, 시간 복잡도가 좋지 않다는 뜻입니다.

투 포인터 알고리즘은 배열을 순회하면서
시작점과 끝점 두 개의 인덱스를 이동시키며 문제를 해결하는 방식입니다.

예를 들어?

구간의 합이 10이 되는 경우를 찾는 문제를 생각해 보겠습니다.

투 포인터를 사용하지 않는다면 보통 다음과 같은 방식으로 접근하게 됩니다.

배열의 시작점을 하나 정합니다.
끝점을 하나씩 늘려 가며 구간 합을 구합니다.
가능한 모든 구간을 확인합니다.
합이 10인 경우가 나오면 정답을 1 증가시킵니다.

예를 들어 1부터 10까지의 배열이 있다고 해보겠습니다.

투 포인터를 사용하지 않으면 보통 2중 반복문으로
모든 구간의 합이 10인지 하나씩 확인하게 됩니다.

이 방식은 가능한 모든 구간을 확인해야 하므로
시간 복잡도가 O(N²) 이 됩니다.

누적합을 사용하더라도 모든 구간을 이중 반복문으로 순회하면
결국 전체 시간 복잡도는 크게 줄지 않습니다.
즉, 구간 합 계산은 빨라졌더라도 구간의 개수 자체가 너무 많기 때문입니다.

그래서 투 포인터

그렇다면 위와 같은 비효율적인 방식 대신
투 포인터 알고리즘을 사용하면 어떻게 될까요?

기본 아이디어는 다음과 같습니다.

시작점(start)과 끝점(end)을 0으로 둡니다.
현재 구간의 합을 확인합니다.
합이 M과 같으면 정답을 1 증가시킵니다.
합이 M보다 작으면 끝점을 오른쪽으로 이동합니다.
합이 M보다 크거나 같으면 시작점을 오른쪽으로 이동합니다.

이 방식은 매번 모든 구간을 다시 확인하지 않고,
두 포인터를 한 방향으로만 이동시키며 탐색하기 때문에 훨씬 효율적입니다.

단, 이 방식은 배열의 원소가 모두 양수일 때 특히 효과적입니다.
현재 합이 작으면 끝점을 늘렸을 때 합이 커지고,
현재 합이 크면 시작점을 옮겼을 때 합이 작아진다는 성질을 이용하기 때문입니다.

in Kotlin

투 포인터는 보통 while 문으로 구현합니다.
아래 예시는 백준 2003번 문제입니다.

문제에서는 n개의 수로 이루어진 수열에서
A[i] + A[i+1] + ... + A[j]가 m이 되는 경우의 수를 구해야 합니다.

import java.io.StreamTokenizer

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun nextInt(): Int {
        nextToken()
        return nval.toInt()
    }

    val n = nextInt()
    val m = nextInt()

    // 1. 누적합 배열 생성
    val pSum = IntArray(n + 1)
    repeat(n) { idx ->
        pSum[idx + 1] = pSum[idx] + nextInt()
    }

    var ans = 0
    var start = 0
    var end = 0

    // 2. 투 포인터로 구간 탐색
    while (start <= end && end < n + 1) {
        val sum = pSum[end] - pSum[start]

        if (sum == m) {
            ans += 1
        }

        if (sum < m) {
            end += 1
        } else {
            start += 1
        }
    }

    println(ans)
}