[백준] 2467 용액

문제 설명

문제 링크

또 하나의 이분 탐색 문제이다. 기존에 하던 난이도에서 살짝 올려봤다.

용액은 산성과 알칼리성 용액이 있는데 그 중 산성은 음수로, 알칼리성은 양수로 표현되며, 이는 두 번째 줄에 오름차순으로 주어진다. 여기서 두 용액의 값을 더했을 때 가장 0에 근접한 수가 나오는 용액 값 조합을 구하는 문제이다.

문제 풀이

일단 먼저 체크해야 할 것은, 용액이 오름차순으로 주어진다는 점이다. 그러면 여기서 가장 먼저 생각할 수 있는 것은 모든 용액이 산성일 때와 모든 용액이 알칼리성일 때를 분기하여 처리할 수 있다는 점이다.

설령, 모든 용액이 산성(음수)이라고 가정해보자. 가장 마이너스인 값이 맨 왼쪽에 나오고 0에 가장 근접한 값이 맨 오른쪽에 나올 것이다. 그러면 분명 가장 오른쪽의 두 값의 합이 0에 근접한 조합일 것이다. 반대로, 모든 용액이 알칼리성(양수)라고 가정한다면 맨 왼쪽의 두 수의 합이 0에 제일 근접할 것이다. 이를 코드로 표현하면 다음과 같다:

if sol[0] >= 0 and sol[-1] >= 0:
    ans = [sol[0], sol[1]]
elif sol[0] <= 0 and sol[-1] <= 0:
    ans = [sol[-2], sol[-1]]

ans에 두 용액의 특성값을 저장하여 이를 출력한다면 위와 같은 형식으로 분기가 가능하다.

여기까지만 하면 이분 탐색이 아닐터. 보통의 경우에는 양수와 음수가 같이 나올 것이다. 그러면 여기서 생각을 해볼 수 있다:

가장 0이랑 근접한 양수 하나와 음수 하나를 정하면 되는 것이 아닐까?

아쉽게도 아니다. 만약 용액의 특성값들이 다음과 같이 나온다고 생각해보자: -100000, -2000, 8000, 100000
이렇게 나오면 0과 가장 근접한 음수와 양수값 -2000과 8000이 답이 아니고, -100000, 100000가 답이 된다.

그러면 이 값들이 균일한 차로 주어지지 않는 상황에서, 무작정 탐색 및 비교 범위를 반으로 나누고 한 쪽을 배제할 수 있을까? 아니라고 생각한다. 하는 수 없이 왼쪽 끝과 오른쪽 끝을 조건에 따라 하나씩 이동해가며 둘의 합을 구하고, 이를 기존에 저장해둔 최소합과 비교해보는 수밖에 없다.

이러면 시간이 오래 걸릴 수도 있기 때문에 두 용액의 합이 0인 경우에는 무조건 정답인 관계로 이 또한 다음과 같이 분기해주었다:

compare_diff = sol[lt] + sol[rt]
if compare_diff == 0:
    ans = [sol[lt], sol[rt]]
    break

입력받은 특성값의 배열을 solution의 약자인 sol로 하고, lt를 0, rt를 N-1으로 설정하였으며, sol[0] + sol[-1]을 초기 합 diff로 설정했다. 지금 생각해보니 sum이라고 해도 괜찮았을 것 같다…

이후, 변경되는 lt와 rt값에 따라 새로운 합(차?)을 구하고, 이 합의 절대값이 기존에 저장된 합의 절대값보다 작으면 갱신해주었다. 이 절대값을 씌워야한다는 생각을 처음엔 하지 못하여 계속 가장 절대값이 큰 음수가 나오는 소소한 트러블도 있었다.

lt와 rt를 다시 설정하는 과정은, 만약 두 특성값의 합이 양수이면 rt가 더 컸다는 뜻이니 rt -= 1을 해주었고, 반대의 경우에는 lt += 1을 해주었다.

코드

import sys
input = sys.stdin.readline

#오늘은 이분탐색만 노린다

#용액의 개수
N = int(input())

#용액의 특성값: 오름차순으로 입력된다.
sol = list(map(int, input().split()))
diff = sol[0] + sol[-1]
ans = [sol[0], sol[-1]]

#만약 모든 수가 양수이거나 음수이면 아래 조건문에 따라 연산 시간을 단축할 수 있다. 
if sol[0] >= 0 and sol[-1] >= 0:
    ans = [sol[0], sol[1]]
elif sol[0] <= 0 and sol[-1] <= 0:
    ans = [sol[-2], sol[-1]]
else:
    lt = 0 
    rt = N-1

    while lt < rt:
        compare_diff = sol[lt] + sol[rt]
        if compare_diff == 0:
            ans = [sol[lt], sol[rt]]
            break
        elif abs(compare_diff) <= abs(diff):
            ans = [sol[lt], sol[rt]]
            diff = compare_diff

        if compare_diff >= 0:
            rt -= 1
        else:
            lt += 1 

print(*ans)