[백준(파이썬/Python)] 두 용액 - 이분탐색, 투포인터

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

'맞왜틀'을 엄청 반복했던 문제입니다... 이 문제에서 약간 트릭(?)이었다고 생각하는 부분은 산성과 알칼리 용액이 모두 존재했을 때에도 한 종류의 용액 두 개를 골라 혼합했을 때가 최적해가 될 수 있다는 것입니다.

 

예를 들어 -100, -50, 1, 2라고 주어졌을 때 정답은 1+2 = 3이 되어야 하는데, 잘못 생각하면 abs(-50 + 2) = 48 이라고 생각할 수 있는 것이죠.

 

두번째로, 저는 이 문제에서 투 포인터를 사용했습니다. 이분 탐색으로도 풀려고 시도해봤지만, 이분탐색으로 풀 때 필요한 "어떤 값 X에 가장 가까운 값 찾기" 과정이 약간 번거롭게 느껴졌기 때문입니다(이분탐색을 이용한 풀이도 아래에 첨부한다).

 

투 포인터는 주어진 배열 내에서 어떠한 조합을 찾을 때, O(N^2)으로 완전탐색을 하지 않고, O(N)의 시간복잡도 안에서 탐색을 할 수 있게 해줍니다.

 

이 문제 같은 경우에도 용액의 특성값을 모두 liquid 리스트로 입력받고 정렬한 뒤, 왼쪽 끝과 오른쪽 끝부터 좁혀오면서 모든 경우를 탐색할 수 있죠.

 

단, "투 포인터를 사용할 때는 언제 어느쪽 포인터를 움직일 것인가?"가 중요한데 이 문제에서는 두 용액의 특성값 합이 음수일때는 특성값의 합을 0에 가까운 수로 늘려보기 위해 왼쪽 포인터를 안쪽으로 움직이고, 그 반대의 경우에는 오른쪽 포인터를 움직이도록 구현했습니다.

 

이렇게 포인터를 서로 교차할 때까지 움직여보면서 두 특성값 합의 절대값이 0에 가까운 지점에서 기록을 하고, 최종적인 정답을 리턴해주면 됩니다!(두 용액 특성값 합이 0이 되는 지점을 만나면 더 좋은 정답이 없으므로 탐색을 종료).

 

[풀이 - 투 포인터]

import sys
input = sys.stdin.readline

answer = []
n = int(input())
liquid = list(map(int, input().split()))
liquid.sort()
# 산성 용액으로만 이루어진 경우
if liquid[0] > 0:
    answer.extend(liquid[:2])

# 알칼리 용액으로만 이루어진 경우
elif liquid[-1] < 0:
    answer.extend(liquid[-2:])


# 산성, 알칼리 용액이 둘 다 있는 경우
# 주의) 이 경우에도 산성, 알칼리 용액만으로 최소값을 만들 수 있다.
else:
    # 투 포인터 이용
    left, right = 0, len(liquid) - 1
    min_diff = 2000000001
    while left < right:
        diff = liquid[left] + liquid[right]

        if abs(diff) < min_diff:
            answer = [liquid[left], liquid[right]]
            min_diff = abs(diff)

        if diff > 0:
            right -= 1
        
        elif diff < 0:
            left += 1
        
        else:
            break
print(*answer)

 

[풀이 - 이분탐색]

import sys
from bisect import bisect_left
input = sys.stdin.readline


# target과 가장 가까운 숫자를 리턴
def findClosestNum(array, target):
    index = bisect_left(array, target)
    if index == 0:
        return array[index]
    
    if index == len(array):
        return array[-1]

    left = array[index-1]
    right = array[index]

    if target-left < right - target:
        return left
    return right

answer = []
n = int(input())
plus, minus = [], []
for l in list(map(int, input().split())):
    plus.append(l) if l > 0 else minus.append(l)
plus.sort()
minus.sort(reverse=True)

# 산성 용액으로만 이루어진 경우
if len(plus) == 0:
    answer = minus[:2][::-1]

# 알칼리 용액으로만 이루어진 경우
elif len(minus) == 0:
    answer = plus[:2]

# 산성, 알칼리 용액이 둘 다 있는 경우
# 주의) 이 경우에도 산성, 알칼리 용액만으로 최소값을 만들 수 있다.
else:   
    minSum = 2000000001
    if len(minus) > 1:
        tempSum = abs(sum(minus[:2]))
        if tempSum < minSum:
            minSum = tempSum
            answer = minus[:2][::-1]

    if len(plus) > 1:
        tempSum = sum(plus[:2])
        if tempSum < minSum:
            minSum = tempSum
            answer = plus[:2]

    for m in minus:
        closestNum = findClosestNum(plus, -m)
        tempSum = abs(m + closestNum)
        if tempSum < minSum:
            minSum = tempSum
            answer = [m, closestNum]
print(*answer)