BaekJoon2467_용액

문제

풀이

이 문제는 두 가지 방법으로 풀 수 있다.
투 포인터 방법과 이진탐색 방법인데 투 포인터 방식은 간단하게 생각하면 금방 떠올릴 수 있다. 처음과 끝에서 시작해서 값을 비교해가며 답을 찾아가면 된다.

이진 탐색으로 푸는 방법은 사실상 투포인터 방식과 비슷한데 용액의 i번째 값과 i+1 ~ n까지의 값의 합을 각각 이진탐색으로 구해서 0과 가장 가까운 쌍을 찾는 방식이다.

풀이 코드

투 포인터 방식

import sys
input = sys.stdin.readline

n = int(input())

liq = list(map(int,input().split()))

start = 0
end = n - 1

temp = abs(liq[start] + liq[end])
ans1 = 0
ans2 = n-1
while start < end:
    a = liq[start] + liq[end]
    if abs(a) < temp:
        temp = abs(a)
        ans1 = start
        ans2 = end
        if a == 0:
            break
        
    if a < 0:
        start += 1
    else:
        end -= 1
print(liq[ans1], liq[ans2])

이진 탐색 방식

import sys
input = sys.stdin.readline

n = int(input())
liq = list(map(int,input().split()))

answer = 1000000000000
ans1 = 0
ans2 = 0

for i in range(n-1):
    check = liq[i]
    start = i+1
    end = n-1
    
    while start <= end:
        mid = (start+end)//2
        temp = check + liq[mid]

        if abs(temp) < answer:
            answer = abs(temp)
            ans1 = i
            ans2 = mid
            
            if temp == 0:
                break
            
        if temp < 0:
            start = mid + 1
        else:
            end = mid - 1
            
print(liq[ans1], liq[ans2])