[백준] 백준 Python3 2467번 문제 및 소스코드

문제 링크

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

 

문제

 

소스 코드

import sys
input = sys.stdin.readline

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

ans = float("INF")
ans_left = 0
ans_right = 0

for i in range(n-1):
    current = liquids[i]

    start = i + 1
    end = n - 1

    while start <= end:
        mid = (start + end) // 2
        tmp = current + liquids[mid]

        if abs(tmp) < ans:
            ans = abs(tmp)
            ans_left = i
            ans_right = mid

            if tmp == 0:
                break
        
        if tmp < 0:
            start = mid + 1
        
        else:
            end = mid - 1

print(liquids[ans_left], liquids[ans_right])

 

코드 해설

import sys
input = sys.stdin.readline

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

n : 용액 개수

liquids : 용액들의 리스트 (이미 정렬되어 있다고 가정)

ans = float("INF")     # 현재까지 0에 가장 가까운 값의 절댓값
ans_left = 0           # 그 때의 왼쪽 인덱스
ans_right = 0          # 오른쪽 인덱스

for i in range(n-1):
    current = liquids[i]
    start = i + 1
    end = n - 1

i번째 용액을 고정시키고, 그 이후의 용액들(i+1부터 n-1) 중에서 current + 다른 값이 0에 가까운 쌍을 이진 탐색으로 찾기 위한 설정

    while start <= end:
        mid = (start + end) // 2
        tmp = current + liquids[mid]

현재 liquids[i]와 liquids[mid]의 합을 구한다.

그리고 이 값이 0에 가까운지 체크한다.

        if abs(tmp) < ans:
            ans = abs(tmp)
            ans_left = i
            ans_right = mid

            if tmp == 0:
                break

abs(tmp)가 기존의 ans보다 작으면(=더 0에 가까우면) ans를 갱신하고, 두 용액의 인덱스를 저장.

합이 0이면 바로 종료(최적이니까)

        if tmp < 0:
            start = mid + 1
        else:
            end = mid - 1

만약 합이 음수면 더 큰 값을 골라야 하므로 오른쪽으로 이동

합이 양수면 더 자은 값을 골라야 하므로 왼쪽으로 이동

print(liquids[ans_left], liquids[ans_right])