[Python] 백준3273번 : 두 수의 합

💡문제

백준 3273번 문제 링크

🍀풀이

시간초과 코드

n = int(input())

arr = list(map(int, input().split()))

x = int(input())
cnt = 0

for i in range(n):
    for j in range(i + 1, n):
        if arr[i] + arr[j] == x:
            cnt += 1

print(cnt)

역시나 안될걸 알았지만 시간초과가 났다... 시간복잡도 O(n^2)...
그래서 보니까 투 포인터로 푸는거였다.
그래도 이 방법으로 꽤 풀었는데 왜 매번 기억이 안나지...

정답 코드

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)

left가 배열의 왼쪽 인덱스, right가 배열의 오른쪽 인덱스다.
x와 두 수의 합을 비교해서 좌우 인덱스들을 옮겨간다.

1. 두 수의 합이 x와 같으면 쌍의 개수 +1을 하고 left +1을 해서 다음 값을 찾는다.
2. 두 수의 합이 x보다 작으면 left를 +1을 해서 더 큰 수를 더한다.
3. 두 수의 합이 x보다 크면 right를 -1 해서 더 작은 수를 더한다.

이런식으로 해서 값을 구하는 형식이다!

서현언니 코드

n = int(input())
seq = input().split()
x = int(input())

max_value = 1000000
arr = [0] * (max_value + 1)

result = 0

for i in range (0, n):
    num = int(seq[i])
    y = x - num
    if 0 <= y <= max_value and arr[y] == 1:
        result += 1
        arr[num] = 1
    else:
        arr[num] = 1
print(result)

코테 리뷰 하면서 서현이 언니 코드 리뷰를 들었는데 와 진짜 좋은 코드....
필요한 쌍의 값과 방문여부를 확인해서 하는 코드...
시간복잡도도 더 적다 O(n)!!