[투 포인터/Python] 3273번: 두 수의 합 - 효과는 굉장했다!

3273번: 두 수의 합

 

알고리즘 분류

• 정렬
• 두 포인터

 

 

SOLUTION

import numbers
import sys

n = int(sys.stdin.readline())
nums = sorted(list(map(int, sys.stdin.readline().split())))
x = int(sys.stdin.readline())

# 양 끝에 탐색 시작 포인트를 둔다
start, end = 0, n-1
cnt = 0

while start < end:
    tmp = nums[start] + nums[end]
    # 배열은 정렬된 상태이므로 조건을 만족하면 수가 작은 쪽인 start부분의 포인트를 움직여준다.
    if tmp == x:
        cnt += 1
        start += 1

    elif tmp > x:
        end -= 1

    else:
        start += 1

print(cnt)

 

※ Two Pointer는 배열의 양 끝부분에서 순차적으로 탐색하므로 O(N)의 시간 복잡도를 가진다.

만약, 순차적으로 배열을 탐색하면서 만족하는 쌍을 구하면 O(N^2)의 시간 복잡도를 가지므로 시간 초과가 난다.