🔗 문제 링크
https://www.acmicpc.net/problem/2470
💻 코드
import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int,input().split()))
result = [0,0]
total = float('inf')
nums.sort()
left,right = 0,n-1
while left < right:
tot = nums[left] + nums[right]
if abs(tot) < total:
result = [nums[left],nums[right]]
total = abs(tot)
if tot == 0:
break
elif tot < 0:
left += 1
else:
right -= 1
print(*result)🤷♂ 풀이
투포인터로 풀어주는데, 배열을 정렬시킨다.
left는 배열의 첫 요소, right는 마지막 요소를 가리키게 한다.
left < right 일때까지만 반복하게하며, 값의 합에 따라 왼쪽 포인터를 이동시킬건지 오른쪽 포인터를 이동시킬건지 정한다.
모든 조합을 탐색하면 O(n^2)의 시간복잡도를 가지기에 정렬 O(nlogn) 후 한 번의 루프 O(n)만으로 해결한다.
전에 풀었던 문제들은 슬라이딩 윈도우 크기를 동적으로 조정해 조건을 만족하는 연속된 부분을 찾는 것이었고, 이 문제는 최적의 두 수를 찾는 것이다.
최적의 두 수를 찾는 것이고 단일값을 찾는 건 아니기에 이분 탐색보다는 투 포인터가 적합하다.