[백준] 3273 두 수의 합 / 파이썬(Python)

문제

투 포인터를 이용하여 푸는 문제이다. 이 문제를 풀기 전에는 투 포인터를 몰랐다.

물론 투 포인터가 아니어도 풀 수 있는 문제지만, 시간 제한에서 막히기 때문에 투 포인터를 써야 한다.

시간 초과 난 코드

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
x = int(input())

cnt = 0
for i in range(len(arr)-1):
    a = arr[i]
    for j in range(i, len(arr)):
        if arr[j] == x - a:
            cnt +=1

print(cnt)

이중 반복문으로 풀었지만 시간 복잡도가 $O(n)$이라서 시간 초과가 뜬다.

투 포인터로 풀려면 일단 배열을 입력받을 때 정렬을 해야 한다.
배열의 양쪽 끝에서 포인터를 지정하고 값에 따라 포인터를 움직인다.

투 포인터가 가리키는 인덱스에 위치하는 요소의 합이 x와 같으면 cnt를 증가시키고 왼쪽 포인터를 증가시킨다. (오른쪽 포인터 값을 감소시켜도 무방함)
x보다 값이 작으면 왼쪽 포인터 값을 증가시킨다. 더 큰 값을 더하기 위해서다.
x보다 값이 크면 오른쪽 포인터 값을 감소시킨다. 더 작은 값을 더하기 위해서다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
n = int(input())
arr = sorted(list(map(int, input().split())))
x = int(input())

cnt = 0
left, right = 0, n-1
while left < right:
    num = arr[left] + arr[right]
    if (num == x):
        cnt +=1
        left += 1
    elif num < x:
        left += 1
    else:
        right -= 1
        
print(cnt)