[BOJ] 2470번 - 두 용액

📜 문제

용액의 개수와 각 용액의 특성값이 주어졌을 때, 두 용액의 특성값을 합친 값이 0이거나 0에 가장 가까운 용액 두 개를 찾는 문제

문제 접근

처음 접근은 왼쪽 포인터와 오른쪽 포인터를 두고, 두 포인터에 해당하는 용액의 특성값의 합의 절대값이 기존 합의 최소값보다 클 경우 오른쪽 포인터를 한 칸 왼쪽으로 이동시키고, 반대의 경우에는 왼쪽 포인터를 오른쪽으로 한 칸 이동 시켰다.

코드 1

첫번째 접근 방식으로 풀이했을때, 코드를 다음과 같이 짰다.

N = int(input())

liquid = sorted(list(map(int, input().split())))
min_val = abs(liquid[0] + liquid[-1])
min_left = 0
min_right = N-1
def juicy(left, right):
    if left >= right:
        return
    a = abs(liquid[left] + liquid[right])
    global min_val, min_left, min_right
    if min_val > a:
        min_val = a
        min_left, min_right = left, right
    if abs(liquid[left+1]+liquid[right]) < a:
        juicy(left+1, right)
    if abs(liquid[left]+liquid[right-1]) < a:
        juicy(left, right-1)

juicy(0, N-1)
print(liquid[min_left], liquid[min_right])

계속 풀이를 하다보니, 이 방식은 아예 틀린 접근이라는 것을 알 수가 있었다.
데이터가 [-98 -97 -1 1 2 99] 이런식으로 들어왔을 경우, -1, 1이 정답인데 포인터가 -97, 99에서 더 이상 값을 개선하지 못하게 된다. 왼쪽 포인터와 오른쪽 포인터를 한 번에 한 칸씩 갱신하기 때문에 더 안쪽에 정답이 있어도 특성값의 합의 절대값이 더 크게 나와버려 로직이 종료되는 현상이 발생한다.

문제 접근 2

기존 접근 방식에서 문제점을 발견한 후, 이를 개선하기 위해서 특성값의 합의 절대값에 따라 포인터를 이동시키는 것이 아닌, 특성값의 합에(절대값 아님)따라서 포인터를 이동시키는 접근 방식을 떠올렸다.

코드 2

N = int(input())
liquid = list(map(int, input().split()))
liquid.sort()

min_value = liquid[0]+liquid[-1]
left, right, min_value, ans = 0, N-1, liquid[0]+liquid[-1], (0, N-1)
while left < right:
    a = liquid[left]+liquid[right]
    if abs(a) < abs(min_value):
        min_value = a
        ans = (left, right)
    if not a:
        print(liquid[left], liquid[right])
        exit()
    if a > 0:
        right -= 1
    else:
        left += 1
print(liquid[ans[0]], liquid[ans[1]])