[Baekjoon]2467. 용액

Algorithm

binary search

How to Solve

Constraint

• 시간: 1초
• 메모리: 128 MB
• 2 <= N <=100,000

Method

1. 완전탐색의 경우
   N * (N-1)번 탐색 = 10,000,000,000 -> 불가능, 시간 초과
2. 이진탐색의 경우
   O(log N) = 16.6
   (start+end)<0인 경우: start+1
   (start+end)>0인 경우: end-1

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))


start, end = 0, N-1 # 초기값 설정
min_dif = abs(arr[start] + arr[end]) # 합의 최솟값을 저장할 변수 min_dif
a, b = arr[start], arr[end]

while start < end:
    target = arr[start] + arr[end]
    # 합이 최솟값일 경우 min_dif, a, b 갱신
    if abs(min_dif) > abs(target):
        min_dif = abs(target)
        a, b = arr[start], arr[end]
    if target == 0:
        break
    elif target < 0:
        start += 1
    elif target > 0:
        end -= 1
print(a, b)