백준 | 두 수의 합

백준 두 수의 합

combinations()를 활용한 코드는 시간 초과가 뜬다..

N개의 원소 중에서 2개를 뽑는 경우의 수는 N * (N - 1) / 2인데, n이 100,000일 경우에는 약 5 * 10^9개의 조합이 생성될 수 있어 1초를 넘을 수 있다.

# 오답(시간 초과)


import sys
from itertools import combinations


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

result = 0
for case in combinations(arr, 2):
    if sum(case) == x:
        result += 1

print(result)

투 포인터 알고리즘을 쓰면, 위의 시간 복잡도 O(N^2)을 O(NlogN)으로 줄일 수 있다.

# 정답


import sys


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

# 투 포인터 알고리즘을 사용하기 위한 정렬
arr.sort()

left = 0
right = n - 1
result = 0

while left < right:
    sum_num = arr[left] + arr[right]

    if sum_num == x:
        result += 1
        left += 1
        right -= 1
    elif sum_num < x:
        left += 1
    elif sum_num > x:
        right -= 1

print(result)