[Python] 백준 - 2470 두 용액

출처: 백준 온라인 저지
https://www.acmicpc.net/problem/2470

---

처음 풀이

from sys import stdin
from bisect import bisect_left


n = int(stdin.readline())
array = [int(x) for x in stdin.readline().split()]
array.sort()

index = bisect_left(array, 0)
acid = array[:index]
alkali = array[index:]


def get_min_value(arr1, arr2):

    if not arr1:
        return arr2[0], arr2[1]

    if not arr2:
        return arr1[-2], arr1[-1]

    i, j = len(arr1) - 1, 0
    min_value = abs(arr1[i] + arr2[j])
    min_set = arr1[i], arr2[j]

    while i >= 0 and j < len(arr2):
        if abs(arr1[i] + arr2[j]) < min_value:
            min_value = abs(arr1[i] + arr2[j])
            min_set = arr1[i], arr2[j]

        value = arr1[i] + arr2[j]

        if value == 0:
            return arr1[i], arr2[j]
        elif value > 0:
            i -= 1
        else:
            j += 1

    if len(arr2) >= 2:
        if arr2[0] + arr2[1] < min_value:
            min_value = arr2[0] + arr2[1]
            min_set = arr2[0], arr2[1]

    if len(arr1) >= 2:
        if abs(arr1[-1] + arr1[-2]) < min_value:
            min_set = arr1[-2], arr1[-1]

    return min_set


a, b = get_min_value(acid, alkali)

print(a, b)

정답이긴 하지만, 사실 더 간단하게 풀 수도 있었던 풀이다. 이 풀이에 대한 상세한 설명을 한 이후, 좀 더 간단한 풀이를 덧붙일 것이다.

처음 풀이 설명

from sys import stdin
from bisect import bisect_left


n = int(stdin.readline())
array = [int(x) for x in stdin.readline().split()]
array.sort()

index = bisect_left(array, 0)
acid = array[:index]
alkali = array[index:]

array 리스트는 용액의 특성값을 저장한다. 이때, 특성값이 음수면 산성 용액이고, 양수면 알칼리성 용액이다. 이 둘을 구분하기 위해

1) array 리스트를 정렬하고
2) 이분 탐색으로 0이 들어갈 인덱스를 찾은 뒤 (bisect_left() 메서드)
3) 해당 인덱스를 기준으로 산성 용액과 알칼리 용액으로 나누었다.

def get_min_value(arr1, arr2):

    # 산성 용액이 없는 경우
    if not arr1:
        return arr2[0], arr2[1]

    # 알칼리성 용액이 없는 경우
    if not arr2:
        return arr1[-2], arr1[-1]

정렬된 산성 용액 리스트와 알칼리 용액 리스트를 인자로 받아서, 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 반환하는 함수를 정의한다.

우선 IndexError를 피하기 위해, 산성 용액이 없는 경우와 알칼리성 용액이 없는 경우를 먼저 처리해준다.

• 산성 용액이 없는 경우, 두 개의 알칼리성 용액의 합이 0에 가장 가까우려면, 가장 작은 두 수를 뽑아야 한다.
• 알칼리성 용액이 없는 경우, 두 개의 산성 용액의 합이 0에 가장 가까우려면, 절대값이 가장 작은 두 수, 즉 가장 큰 두 수를 뽑아야 한다.

    i, j = len(arr1) - 1, 0
    min_value = abs(arr1[i] + arr2[j])
    min_set = arr1[i], arr2[j]

이전에 학습한 투 포인터를 활용하고자 했다. 다만 두 개의 포인터가 각각 산성 용액 리스트, 알칼리성 용액 리스트에서 움직이는 방식이다.

i는 정렬된 산성 용액 리스트 오른쪽 끝에서 시작하여 왼쪽으로 이동하고,
j는 정렬된 알칼리성 용액 리스트 왼쪽 끝에서 시작하여 오른쪽으로 이동한다.

min_value에는 두 용액으로 만드는 0에 가장 가까운 특성값의 절대값을 저장한다.
min_set에는 min_value를 만드는 두 용액의 특성값을 저장한다.

    while i >= 0 and j < len(arr2):
        if abs(arr1[i] + arr2[j]) < min_value:
            min_value = abs(arr1[i] + arr2[j])
            min_set = arr1[i], arr2[j]

        value = arr1[i] + arr2[j]

        if value == 0:
            return arr1[i], arr2[j]
        elif value > 0:
            i -= 1
        else:
            j += 1

현재 탐색 중인 두 용액이 만드는 특성값의 절대값이 min_value보다 작으면,
그 수를 min_value에, 두 용액의 값을 min_set에 저장한다.

그리고 두 용액이 만드는 (절대값이 아닌) 특성값을 value 변수에 저장한다.

• value가 0이라면 min_value도 0이므로 더 이상의 탐색이 불필요하다. 따라서 value를 0으로 만드는 두 값을 바로 리턴한다.

• value가 0보다 크다면, 0에 가까운 값을 만들기 위해서는 더 작은 수가 필요하다. 따라서 산성 용액 리스트의 인덱스를 가리키는 i에 1을 뺀다.

• value가 0보다 작다면, 0에 가까운 값을 만들기 위해서는 더 큰 수가 필요하다. 따라서 알칼리성 용액 리스트의 인덱스를 가리키는 j에 1을 더한다.

위 작업을 탐색을 마칠 때까지 반복한다.

    if len(arr1) >= 2:
        if abs(arr1[-1] + arr1[-2]) < min_value:
            min_set = arr1[-2], arr1[-1]
            
    if len(arr2) >= 2:
        if arr2[0] + arr2[1] < min_value:
            min_value = arr2[0] + arr2[1]
            min_set = arr2[0], arr2[1]
    
    return min_set


a, b = get_min_value(acid, alkali)

print(a, b)

위에서 while문을 통해 탐색을 거의 다 마쳤다. 하지만 while문에서는 하나의 산성 용액과 하나의 알칼리 용액을 더하는 경우만을 살펴보았다. 2개의 산성 용액 혹은 2개의 알칼리 용액이 0에 가장 가까운 값을 만드는 경우도 있다.

첫 번째 if문에서는 산성 용액 2개로 만들 수 있는 0에 가장 가까운 값을 검사한다.

두 번째 if문에서는 알칼리성 용액 2개로 만들 수 있는 0에 가장 가까운 값을 검사한다.

더 간단한 풀이

그런데 사실 위와 같이 산성 용액 리스트와 알칼리성 용액 리스트를 따로 나눌 필요는 없다.

양수, 음수 구분 없이 정렬된 하나의 리스트가 있을 때, 리스트의 양쪽 끝에서 가운데로 가는 투 포인터를 활용하면 된다.

리스트는 정렬되어 있으므로, 두 수의 합이 0보다 크면 오른쪽 인덱스를 왼쪽으로 한 칸 옮기고, 합이 0보다 작으면 왼쪽 인덱스를 오른 쪽으로 한 칸 옮기면 된다.

이렇게 구현하면 양수, 음수 상관없이 0에 가장 가까운 합을 만드는 두 수를 찾을 수 있으므로, 예외 처리의 부담도 줄어든다.

간단하게 다시 구현해 본 코드는 아래와 같다.

from sys import stdin
from bisect import bisect_left


n = int(stdin.readline())
array = [int(x) for x in stdin.readline().split()]
array.sort()


def get_min_value(arr):
    i, j = 0, len(arr) - 1
    min_value = abs(arr[i] + arr[j])
    min_set = i, j

    while i < j:
        current = arr[i] + arr[j]

        if abs(current) < min_value:
            min_value = abs(current)
            min_set = i, j

        if current == 0:
            return min_set
        elif current > 0:
            j -= 1
        else:
            i += 1

    return min_set


a, b = get_min_value(array)

print(array[a], array[b])