PS/BOJ Python
3273번 - 두 수의 합
zpqmdh
2023. 10. 25. 11:56
https://www.acmicpc.net/problem/3273
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
이 문제는 투 포인터를 쓰면 쉽게 풀 수 있다.
하지만, 나는 투 포인터를 써도 시간초과가 났는데...
그 이유는...
# 두 수의 합
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
X = int(input())
answer = 0
start, end = 0, N-1
while start<end:
value = A[start]+A[end]
if value == X:
answer += 1
elif value > X:
end -= 1
else:
start += 1
print(answer)이 코드에서 value와 X가 같은 값일 때, start와 end를 갱신해주지 않아 무한루프에 빠지게 되기 때문이다. 문제에서 X를 만드는 쌍이 몇개냐고 물어보았기 때문에 X를 만든 후에도 포인터를 갱신해주어 남은 리스트를 순회할 수 있도록 수정해줘야한다.
따라서 최종 코드는 아래와 같다.
# 두 수의 합
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
X = int(input())
answer = 0
start, end = 0, N-1
while start<end:
value = A[start]+A[end]
if value == X:
answer += 1
if value >= X:
end -= 1
else:
start += 1
print(answer)