출처 ; https://www.acmicpc.net/problem/2470
문제를 먼저 분석해봅시다
N에 주어진 조건과, 시간 제한을 분석해보겠습니다. N의 경우 100000까지 제한이 되어있고, 시간 제한은 정확하게 1초입니다.
이러한 상황에서, 하나의 리스트에 대해서 2개의 숫자를 뽑아내야하는 문제 유형이기 때문에, 리스트를 두 번 순회하거나(N^2), 혹은 한 번 순회하고, 한 번 탐색하거나(NlogN), 혹은 투포인터로 구현이 가능합니다.
그러나, 시간 제한이 1초이기 때문에 첫번째 방법인, 리스트를 두 번 순회하는 것은 불가능합니다.
그리고, 두번째 방법인, 리스트를 순회하면서 이진 탐색을 하는 방법은 불가능합니다. 이유는 다음과 같습니다.
정확하게 어떤 숫자를 탐색해야하는지 정해진 문제가 아니다
따라서, 저희는 이 문제를 풀 때, 투포인터 기법을 사용해서 접근해야함을 알 수 있습니다.
투포인터 기법을 어떻게 적용할까요?
일단, 투포인터 기법을 효과적으로 적용하기 위해서 우선 리스트를 정렬합니다.
그리고 문제가 원하는 바를 분석해보면, 두 숫자를 더해서 절댓값을 0에 제일 가깝게 만드는것이 목표입니다. 그러면, 절댓값을 어떻게 0에 가깝게 하도록 탐색할 지 전략을 구성해야합니다.
절댓값이 0에 가까워지는 방법은 아래와 같은 방법이 있습니다.
- 0에 가까운 두 음수와 양수를 더한다
- 가장 큰 양수와, 가장 작은 음수를 더한다
- 모두 음수로 구성된 경우에는, 가장 큰 음수 두 개를 더한다
- 모두 양수로 구성된 경우에는, 가장 작은 양수 두 개를 더한다
위를 모두 만족시킬 수 있는 투포인터 전략은, 리스트를 양 쪽에서부터 좁혀오는 방식 입니다.
그렇게 되면, 첫번째 케이스의 경우 중앙에서 만나게 되고, 두번째 케이스는 양 극단에서 값이 결정이 되고, 세번째, 네번째 케이스의 경우 한 쪽에 두개의 포인터가 쏠려서 값이 결정이 됩니다.
따라서, 위의 전략을 구현한 코드를 확인해보겠습니다.
코드를 확인해봅시다
import sys
input = sys.stdin.readline
N = int(input())
liquid = list(map(int, input().split()))
liquid.sort()
left, right = 0, N - 1
answer_left, answer_right = left, right
answer_sum = liquid[left] + liquid[right]
while left < right:
tmp = liquid[left] + liquid[right]
if abs(tmp) < abs(answer_sum):
answer_sum = tmp
answer_left, answer_right = left, right
if answer_sum == 0:
break
if tmp < 0:
left += 1
else:
right -= 1
print(liquid[answer_left], liquid[answer_right])우선, 먼저 answer_sum을 정해주고 시작합니다. 그리고, answer_left, answer_right는 정답이 되는 특성값들의 인덱스를 저장하는 변수입니다.
그리고, 양 방향을 좁혀나가는 투포인터 기법을 위해, while문의 조건은 left < right 로 설정을 해주고, 조건에 따라서 left를 1을 더하거나, right를 1을 빼주면 점점 범위가 좁아지는 효과를 가져옵니다.
반복문을 돌면서. left, right에 해당하는 특성값을 더해서, 기존에 저장된 특성값의 합 절댓값과 서로 비교해주는 과정을 거칩니다. 만일 특성값의 합 절댓값이 기존보다 작은 경우에는, 해당 left, right가 기존의 left, right보다 최적인 경우이기 때문에 answer_left, answer_right를 갱신해줍니다.
그런데, 특성값의 합이 0이 되는 경우에는, 그 케이스보다 최적인 경우는 존재하지 않기 때문에, 반복문을 종료시켜버리고 바로 답을 출력하면 됩니다.
투 포인터 기법을 통한 반복문이 완전히 종료가 되면(특성값의 합이 0이 되는 케이스가 발견되지 않으면), answer_left, answer_right에 저장한 인덱스를 토대로 출력을 해주면 문제 해결은 끝이 납니다.
