[백준] 두 용액

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

분류::이진 탐색 

 

1. 문제 이해 및 해결과정

O(NlogN)

 

 

2. 풀이방법

1) 이진탐색

import sys
sys.stdin = open("input.txt","r")
input= sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))

def find(left, right, x):
    value = arr[left]
    diff = abs(x - value)
    l, r = left + 1, right 

    while l <= r:
        m = (l + r)//2
        curdiff = abs(x-arr[m]) #현재 차이 
        if curdiff < diff : #현재 차이가 작으면 
            value = arr[m]
            diff = curdiff #현재 값으로 
        if arr[m] < x:
            l = m +1
        elif arr[m] > x:
            r = m -1
        else:
            return x
    return value 

sol = abs(arr[0] + arr[1])
a, b = arr[0], arr[1]

for i in range(0, n-1):
    pick = find(i+1, n-1, -arr[i])
    sum = abs(arr[i] + pick)
    if sol > sum : 
        sol = sum
        a, b = arr[i], pick 

print(a,b)

 

3. 오답원인

 

4. 알게된 점