투포인터

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

투 포인터도 이진 탐색과 마찬가지로, 시간 초과의 문제로 완전 탐색을 채택할 수 없을 때 주로 사용합니다.

위와 같은 배열이 있습니다. 우리는 연속된 원소의 합이 5인 부분 배열의 개수를 찾고 싶다고 가정합시다.

그렇다면 우리는 배열의 크기와 인덱스를 모두 바꿔가며 완전 탐색을 해야할까요? 이는 너무 비효율적입니다.

효율성을 위해, 그리고 시간 초과를 방지하기 위해 우리는 투 포인터 기법을 사용할 수 있습니다.

해당 원소를 가리키는 두 개의 포인터를 두고, 조건에 맞게 이동시키는거죠.

합이 5임을 찾고 싶으니 '5보다 작을 땐 아래 쪽 포인터를 이동시키고, 5보다 클 땐 위 쪽 포인터를 이동시키기' 와 같은 규칙을 두면서 말이죠. 하지만 모든 문제가 그렇듯, 응용되면 조건식이 달라지므로 컨셉만 이해하시고 문제로 익히시는게 좋습니다.

완전 탐색으로는 O(N^2)의 시간 복잡도를 가지지만, 정렬(O(NlogN))이 된 상태에서 투 포인터를 사용하면 O(N)의 시간복잡도로 해결할 수 있다는 특징이 있습니다.

문제를 풀어보며 익혀봅시다.

연습문제

BOJ 2467

https://www.acmicpc.net/problem/2467www.acmicpc.net

두 포인터의 시작점이 왼쪽에 위치했던 위 설명에 반해, 이 문제의 두 포인터는 양 끝에 위치합니다.

이 문제에서는 두 개의 포인터가 꼭 동일한 방향으로 이동하지 않아도 된다는 점을 캐치하는 것이 중요합니다.

배열에서 두 원소의 합의 절댓값이 가장 작은 쌍을 찾으면 되는 문제입니다.

다만 유의할 점은, 절댓값이 가장 작은 값이 꼭 (음수, 양수)의 쌍일 필요는 없습니다.

배열에 따라서 (음수, 음수) 혹은 (양수, 양수)도 정답이 될 수 있습니다.

left, right = 0, n - 1
minVal = abs(li[left] + li[right])
ans = [li[left], li[right]]

left와 right가 배열의 양 끝에서 시작하면, 두 원소의 합의 절댓값을 점점 줄여나갈 수 있습니다.

또한, 두 원소의 합의 절댓값을 저장할 minVal 변수와 정답이 될 두 원소의 배열을 초기화해줍시다.

계속해서 진행을 하다가 left와 right가 만날 때 탐색이 종료되어야 하기 때문에,

left, right = 0, n - 1
minVal = abs(li[left] + li[right])
ans = [li[left], li[right]]

while left != right:
    # blah blah

위와 같은 while문을 작성할 수 있습니다.

이후에 left 포인터는 오른쪽으로, right 포인터는 왼쪽으로 향하면서 탐색을 하게 됩니다.

left 입장에서는 오른쪽으로 향할 수록 값이 커지고, right 입장에서는 왼쪽으로 향할수록 값이 작아집니다.

그렇기 때문에, 두 포인터가 가리키는 값의 합이 0에 가장 가까운 쌍을 골라주면 됩니다.

n = int(input())
li = list(map(int, input().split()))
left, right = 0, n - 1
minVal = abs(li[left] + li[right])
ans = [li[left], li[right]]

while left != right:
    if minVal > abs(li[left] + li[right]):  # 최솟값 갱신 조건
        minVal = abs(li[left] + li[right])
        ans = [li[left], li[right]]

    if li[left] + li[right] >= 0:
        right -= 1
    elif li[left] + li[right] < 0:
        left += 1

print(*ans)

전체 코드입니다.

li[left] + li[right] == 0일 경우에 break를 하셔도 무방합니다.

두 가지의 경우를 소개해드렸지만, 다른 방식으로도 사용될 수 있으니 상황에 맞게 판단하셔서 설정하시면 됩니다.

풀어볼 문제

https://www.acmicpc.net/problem/2230www.acmicpc.net

https://school.programmers.co.kr/learn/courses/30/lessons/42885school.programmers.co.kr

[프로그래머스 구명보트]