코딩테스트 대비/단계별 코딩 테스트 준비(27일 과정)
[투 포인터/Python] 3273번: 두 수의 합 - 효과는 굉장했다!
bluetag_boy
2022. 2. 19. 17:10
반응형
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
알고리즘 분류
- 정렬
- 두 포인터
SOLUTION
import numbers
import sys
n = int(sys.stdin.readline())
nums = sorted(list(map(int, sys.stdin.readline().split())))
x = int(sys.stdin.readline())
# 양 끝에 탐색 시작 포인트를 둔다
start, end = 0, n-1
cnt = 0
while start < end:
tmp = nums[start] + nums[end]
# 배열은 정렬된 상태이므로 조건을 만족하면 수가 작은 쪽인 start부분의 포인트를 움직여준다.
if tmp == x:
cnt += 1
start += 1
elif tmp > x:
end -= 1
else:
start += 1
print(cnt)
※ Two Pointer는 배열의 양 끝부분에서 순차적으로 탐색하므로 O(N)의 시간 복잡도를 가진다.
만약, 순차적으로 배열을 탐색하면서 만족하는 쌍을 구하면 O(N^2)의 시간 복잡도를 가지므로 시간 초과가 난다.