백준 3273번 : 두 수의 합 in Python
이 문제는 n개의 서로 다른 양의 정수로 이루어진 수열 내에서 합이 x가 되는 두 수의 쌍의 개수를 구하는 문제이다.
가장 단순한 풀이 방법은 수열의 모든 두 수의 쌍에 대해 합을 구하고 이 합이 x와 같은 경우를 모두 세면 된다. 하지만 이는 모든 두 수의 쌍을 고려해야 하므로 O(n^2)의 시간이 걸린다. 이를 좀더 효율적으로 계산하기 위해 제안된 방법 중 하나가 바로 투 포인터를 이용하는 것이다.
투 포인터는 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 방식이다. 이 문제에서는 수열을 정렬한 뒤, 두 개의 포인터를 수열 양 끝에 두고 특정 조건에 따라 두 포인터를 움직인다. 만약 두 포인터가 가리키는 수의 합이 x보다 작거나 같으면 왼쪽 끝 포인터는 오른쪽으로 한 칸 옮기고, x보다 크면 오른쪽 포인터는 왼쪽으로 한 칸 옮긴다. 이를 두 포인터가 만날 때까지 반복하면서 두 수의 합이 x와 같은 경우를 센다. 이렇게 할 경우 정렬에 들어가는 시간이 O(n logn), 두 개의 포인터를 이용해 비교하는 시간이 O(n)으로 총 O(n logn)의 시간만에 문제를 해결할 수 있다.
그렇다면 어떤 원리로 이 문제를 이러한 방식으로 풀 수 있는 것일까? 수열을 정렬을 해서 두 개의 포인터를 양쪽에 둔다면 왼쪽 끝 포인터는 가장 작은 수를, 오른쪽 끝 포인터는 가장 큰 수를 가리킬 것이다. 여기서 두 수의 합을 구했을 때 x보다 작은 경우를 생각해보자. 그러면 가장 작은 수는 가장 큰 수와 만나도 그 합이 x보다 작으므로 수열 내 각 모든 수와 합쳐도 x보다 작을 것이다. 마찬가지로 x보다 큰 경우에도 가장 큰 수는 가장 작은 수와 만나도 그 합이 x보다 크므로 수열 내 각 모든 수와 합쳐도 x보다 클 것이다. 즉, 굳이 생각할 필요가 없는 두 수의 쌍을 고려하지 않는 것이다. 그러면 더 이상 가장 작은 수(가장 큰 수)를 고려할 필요가 없으므로 왼쪽(오른쪽) 포인터를 오른쪽(왼쪽)으로 한 칸 이동시킨다. 이를 계속 반복하다가 포인터가 만나면 이제 모든 두 수의 쌍을 고려한 것이므로 반복을 중단한다.
문제는 만약 두 수의 합이 x와 같은 경우 어떻게 하느냐인데, 다행히도 이 문제는 수열의 모든 정수가 서로 다르기 때문에, 왼쪽 포인터를 오른쪽으로 옮기던지, 아니면 오른쪽 포인터를 왼쪽으로 옮기던지 둘 중 하나를 선택해 마저 진행하면 된다.
이를 코드로 구현하면 다음과 같다.
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
x = int(input())
# 두 개의 포인터
l = 0
r = n-1
# 수열을 우선 정렬한다.
arr.sort()
# 두 수의 합이 x와 같은 경우의 수
cnt = 0
while l < r:
if arr[l]+arr[r] == x:
cnt += 1
l += 1
elif arr[l]+arr[r] > x:
r -= 1
else:
l += 1
print(cnt)