[파이썬] BOJ_3273(두 수의 합)

 

 

 

문제

 

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

---

 

해설

 

반응형

 

처음에는 밑의 주석처리 된 시간 초과 코드 처럼 풀면 쉽게 해결될 거라고 생각했다.

그치만 이중 반복문을 쓰면 시간복잡도가 O(n^2)이 되어 시간 초과가 난다.

 

이 문제는 투포인터 문제로 리스트의 가장 처음(0)과 가장 마지막(n-1)을 각각 포인터로 설정해

위치를 옮겨가면서 원하는 값을 구하면 된다.

left 위치와 right 위치를 더한 값을 temp에 저장하고

temp가 x와 같다면 만족하는 쌍을 찾은 것이므로 cnt를 +1

left는 right보다 무조건 작은 값인데 둘을 더한 temp가 x보다 작다면 left를 오른쪽으로 한 칸 옮겨

더 큰 값을 넣어 더해준다.

반대로 temp가 x보다 크면 right를 왼쪽으로 한 칸 옮겨 더 작은 값을 넣어 더해주면 된다.

 

 

---

코드

 

-파이썬

#백준 3273(두 수의 합)
import sys
input = sys.stdin.readline
n = int(input())  #수열의 크기
num = [*map(int, input().split())]  #수열
num.sort()
x = int(input())
cnt = 0

# for i in range(n):  #시간 초과 코드
#     for j in range(i+1, n):
#         if num[i] + num[j] == x:
#             cnt += 1
#
# print(cnt)

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