[백준] 2467번 용액 (파이썬)

 

 

 

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

2467번: 용액

이번에는 이진탐색 문제를 풀었다.

2019.06.17 - [Knowledge/Algorithm] - 알고리즘 - 이진탐색 알고리즘 개념

알고리즘 - 이진탐색 알고리즘 개념

이진탐색이 무엇인지 처음 접하는 사람은 위 글을 읽고 오면 좋을 것이다.

 

(참고로 다른사람 풀이를 안보고 풀고 올리는 것이라 효율은 보장하지 않는다. / ("효율 < 직접 풀이" 라고 생각하는 편)

 

이번 문제의 핵심은 bisect 모듈의 응용력이다.

파이썬의 bisect 모듈의 단점은 선택한 데이터가 들어가야할 위치를 반환하는 모듈이라는 것이다.

우리는 찾고자하는 값과 가장 가까운 값을 알기 원하지만

arr = [-1, 30, 100]

라는 배열에서 bisect.bisect(arr, 31)을 하면 2를 반환한다.

그래서 arr[1]의 값이 31보다 작은게 확실하지만 arr[2]의 값이 arr[1]보다 31에 더 가깝다는 보장을 주지 못한다.

그래서 이러한 부분을 고려하고 if문으로 직접 검증해서 인덱스 값을 조정해주었다.

 

import sys
import bisect
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split()))
mini = 2000000000
answer = []
while(True):
    t = bisect.bisect_left(arr, -arr[0])
    if t == len(arr):
        t -= 1
    elif t == 0:
        t = 1
    if t > 1:
        if abs(arr[t] + arr[0]) > abs(arr[t-1] + arr[0]):
            t -= 1
    tmp = arr[0] + arr[t]
    if tmp == 0:
        print(arr[0], arr[t])
        break
    if abs(mini) > abs(tmp):
        mini = tmp
        answer = [arr[0], arr[t]]
    del arr[0]
    if len(arr) == 1:
        print(answer[0], answer[1])
        break

 

 

이 부분이 핵심이라 생각한다.

if t == len(arr):
        t -= 1
    elif t == 0:
        t = 1
    if t > 1:
        if abs(arr[t] + arr[0]) > abs(arr[t-1] + arr[0]):
            t -= 1

범위의 오류를 처리하고 반환값의 왼쪽의 값과 검증을 통해 인덱스값을 조정해주면

쉽게 원하고자 하는 값과 가장 근사한 값을 알 수 있게 된다.