[백준] 2470번. 두 용액

아이디어

• 처음에 무식하게 이중 for문 돌려서 다 찾았더니 시간초과남
• 투포인터와 이분탐색을 섞어서 두 용액의 합이 음수일때는 음수를 줄여주고, 양수일 때는 양수를 줄여주면서 최솟값을 찾아나간다.

• while문에 종료조건을 넣는대신 while start < end:로 조건을 합치는 방법도 있다!

시간복잡도

• O(logN)

코드

1. 재귀 이용

from collections import deque
import sys
input = sys.stdin.readline

def binary_search(l_list, start, end):
    global answer, min_sum

    # 종료 조건
    if start >= end:
        return None
    
    # 두 용액의 합이 제일 작은 것을 찾는다
    l_sum = l_list[start] + l_list[end]
    if abs(l_sum) < min_sum:
        min_sum = abs(l_sum)
        answer = [l_list[start], l_list[end]]

    # 합이 -면 -가 더 큰거니까 하나 큰 걸로 옯겨준다.
    if l_sum < 0:
        binary_search(l_list, start + 1, end)
    
    # 반대면 +가 더 큰거니까 하나 작은걸로 옮겨준다.
    else:
        binary_search(l_list, start, end - 1)


n = int(input())
l_list = list(map(int, input().split()))
num = 1000000000
answer = [0, 0]
min_sum = 9999999999

l_list.sort() # 정렬
# 찾으러 가기
binary_search(l_list, 0, n-1)
answer.sort()
print(*answer)

2. while문 이용

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
l_list = list(map(int, input().split()))
answer = [0, 0]
min_sum = 9999999999

l_list.sort() # 정렬
# 찾으러 가기
start, end = 0, n - 1

while True:
    # 종료 조건
    if start >= end:
        break
    
    # 두 용액의 합이 제일 작은 것을 찾는다
    l_sum = l_list[start] + l_list[end]
    if abs(l_sum) < min_sum:
        min_sum = abs(l_sum)
        answer = [l_list[start], l_list[end]]

    # 합이 -면 -가 더 큰거니까 하나 큰 걸로 옯겨준다.
    if l_sum < 0:
        start += 1
    
    # 반대면 +가 더 큰거니까 하나 작은걸로 옮겨준다.
    else:
        end -= 1

answer.sort()
print(*answer)