[Two Pointers] boj_2470: 두용액

Two Pointers: 두용액(boj_2470)

문제 링크: https://www.acmicpc.net/problem/2470

input: 5(리스트 갯수)
: -2 4 -99 -1 98 (리스트 넘버)

output: -99 98

문제 이해

두 용액 문제는 -100,000,000 부터 100,000,000 까지의 숫자들을 용액으로 리스트에 나타내고 그 중 두가지를 용액의 합이 0에 가장 가까운 두 용액을 찾아내는 것이다.

예를 들면 -2 | 4 | -99 | -1 | 98 이라는 용액들이 있다고 할 때, 두 용액의합이 0에 가장 가까운 두 수는 -99 와 98 이다.

총 100,000개의 리스트가 있을 수 있다고 가정하여 문제를 풀어보자.

접근 방법

투 포인터로 접근을 시도하려면 가장 작은 수 와 가장 큰 수를 기본적으로 찾아야한다. 그러므로 모든 수를 접근할 때 마다 가장 작은 수와 큰 수를 찾는 것은 시간복잡도가 많이 복잡해질 것이다.

그러하여 가장 먼저 정렬을 이용해 리스트를 -99 | -2 | -1 | 4 | 98 의 형태로 만들어보자.

[-99, -2, -1, 4, 98]

그리고 가장 작은 수 -99를 L로 가장 큰수 98을 R로 지정한 후 둘의 합으로 조건을 만들면서 푸는 것이다.

L = -99
R = 98

우리가 찾는 것은 L과R의 합이 0에 가까운 것이기 때문에 만약 L+R이 0이라면 바로 L과R을 출력하면 된다.

if L + R == 0: print(L,R)

만약 L+R의 합이 0보다 작다면(음수), 해당 L의 숫자와 현재 R보다 작은 수들(즉, R보다 작은 R의 후보들)과의 합은 더 작을 것이다.
즉 현재 L은 해당 리스트에서 제거가 되어도 된다. 왜냐하면 남아있는 어떠한 수들과 더하더라도 현재 R(98)과의 합보다는 0과 멀어질 것이기 때문이다.

elif L + R < 0:
L+=1

같은 이유로 L+R의 합이 0보다 크다면, 더 이상 현재 R은 다른 수들과의 합을 볼 필요가 없어진다. 즉 리스트에서 제거해도 된다는 뜻이된다.

elif L + R > 0:
R-=1

어는 순간 L과R의 숫자가 같은 숫자이거나 L이 R보다 커지는 순간 loop에서 나오면 된다. 그리고 두 용액의 합중 0에 가장 가까웠던 용액의 숫자를 출력하면 된다.

코드 & 결과

import sys
si = sys.stdin.readline

N = int(si())
a = sorted(list(map(int,si().split())))

ansL = 1000000000
ansR = -1000000000
sum = 2000000000
L = 0
R = N-1
while L < R:
    if a[L] + a[R] == 0:
        ansL = a[L]
        ansR = a[R]
        break
    elif a[L] + a[R] < 0:
        if abs(a[L]+a[R]) < sum:
            ansL = a[L]
            ansR = a[R]
            sum = abs(a[L]+a[R])
        L+=1
    else:
        if abs(a[L]+a[R]) < sum:
            ansL = a[L]
            ansR = a[R]
            sum = abs(a[L]+a[R])
        R-=1
    
print(ansL,ansR)