백준 3273 두수의 합 Python 투포인트 실버3

반복문을 두 개를 이용하기에는 n의 수가 아주 크기 때문에 시간복잡도가 기하급수적으로 올라간다 => 투 포인터 알고리즘을 사용해서 풀이

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
arr.sort()
# print(arr)
x = int(sys.stdin.readline())
start = 0
end = n-1
cnt = 0
while start < end:
    if arr[start] + arr[end] == x: cnt += 1
    if arr[start] + arr[end] <= x: start += 1
    else: end -= 1
print(cnt)

실수한 점

n이 될수 있는 수가 굉장히 큰 수인 (1 ≤ n ≤ 100000) 범위안에 있다.
반복문을 두개 쓸 경우 시간복잡도가 O(n^2) 이기 때문에 시간 초과가 뜨게 됨
=> 시간 복잡도를 고려해서 적합한 알고리즘을 선택해야 하는데, 경험이 부족했는듯 하다.

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
arr.sort()
x = int(sys.stdin.readline())
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if arr[i] + arr[j] == x:
            cnt += 1
            break

print(cnt)