Algorithm/구현
[백준] 3273번 두 수의 합 (투포인터 문제)
HANNI하니
2023. 11. 2. 15:44
사용 언어 - Python3
문제 - 3273번 두 수의 합
투포인터 : 가능성을 지워주는 방법
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
정답
양쪽 끝에서 비교하면서 만나면 종료
arr[s] + arr[e]
완전탐색 방법) 첫번째 숫자랑 2~n번째 숫자 더해주기 + 두번째 숫자랑 3~n번째 숫자 더해주기....
=> 시간 복잡도 문제 !
투포인터 알고리즘 활용
arr 정렬 후, s = 0 시작지점 / e = n-1 끝지점
arr[s] + arr[e] 가 x라면, cnt += 1
x이상이라면, 마지막 커서를 한 칸 왼쪽으로 이동해준다.
아니라면, 왼쪽 커서를 한 칸 오른쪽으로 이동해준다.n = int(input())
arr = sorted(list(map(int,input().split())))
x = int(input())
s = 0
e = n-1
cnt = 0
while s < e: #만나면 멈춰라
# 정답조건
if arr[s] + arr[e] == x:
cnt += 1
if arr[s] + arr[e] >= x:
e -= 1
else:
s += 1
print(cnt)
레퍼런스
- 깃허브 정답