[백준_2470] 중, 이분 탐색, 두 용액

[백준_2470] 중, 이분 탐색, 두 용액

 

 

산성 용액과 알칼리성 용액은 각각 양수와 음수의 특성값을 가지고 있다. 두 용액을 섞어 0에 가깝게 만들려고 할 때, 용매 각각의 특성값을 출력하는 문제이다.

이 문제는 처음에도 그렇고 풀고 나서도 그렇고 이분 탐색인지 직관적으로 와닿지 않는다는 게 어려웠다.

처음에 '이전의 start와 end의 합'과 'start index +1', 'end index -1'일 때 각각과 비교해 차이가 더 작은 방향으로 움직여야 한다고 생각했다.

그런데 이렇게 했을 때 문제는 [-95, -4, 3, 100]과 같은 경우 답이 -95, 100으로 출력된다는 점이다.

 

문제를 푸는 핵심 포인트는 정렬 후 양쪽에서 0의 방향으로 진행하는 부분(이진 탐색)

합이 양수인지 음수인지에 따라 start와 end가 변한다는 점이다. (이 부분을 캐치하지 못해 못 풀었다.)

 

 

풀이

 

1. 입력받은 용액 특성값을 sort()로 차례대로 정렬

2. 인덱스로 쓰기 위해 start = 0, end = n-1을 부여하고 출력을 위해 저장값 cstart = start, cend = end로 시작한다.  prior_mix는 start, end 인덱스를 가지는 특성값 합의 절대값이다.

3. while start < end: 조건을 가진 while문을 진행한다. 합이 양수인 경우 end -= 1 을 이용하여 양수값을 줄이고, 합이 음수인 경우 start += 1을 이용하여 음수값의 절대값을 줄인다. prior_mix 값이 현재의  abs(arr[start] + arr[end]) 보다 큰 경우 start값을 cstart에, end값을 cend에, abs(arr[start] + arr[end])값을 prior_mix에 저장한다. 

4. prior_mix ==0 즉, 두 용액의 합이 0이거나 start >= end가 되면 종료한다.

 

정답 코드

 

import sys

N = int(input())
arr = [int(x) for x in sys.stdin.readline().split()]
arr.sort()

start = 0
end = N-1
cstart = start
cend = end

prior_mix = abs(arr[start] + arr[end])

while start < end:
    
    if prior_mix > abs(arr[start] + arr[end]):
        cstart = start
        cend = end
        prior_mix = abs(arr[start] + arr[end])
        if prior_mix == 0:
            break
        
    if arr[start] + arr[end] > 0:
        end -= 1
    else:
        start += 1
    
print(arr[cstart], arr[cend])