[백준] 2470번: 두 용액(Python, Binary Search)

문제 링크

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

2470번: 두 용액

 

풀이

풀이 설명

* 분류: 이분탐색(?)

• 카테고리는 이분탐색이지만 정렬로도 해결 가능해서 딱히 쓰진 않았다..
• 더했을 때, 가장 0에 가까운 조합 2개를 뽑는 것
• --, ++, -+ 의 조합일 수 있음
• -99 +99 와 같이 합이 0이 되려면 절대값이 같으면 된다.
• 그러므로 인접한 값을 더한 덧셈배열(diff) 만들어서 절대값을 기준으로 정렬한다. 이때 두 원소 중 한개의 인덱스도 같이 넣어준다.
  • 합쳐서 0이 되는 숫자가 있으면 바로 diff[0] = 0이 된다.

for i in range(1, n):
    temp = array[i] + array[i-1]
    diff.append((temp, i)) #i, i-1
    
diff.sort(key=(lambda x: abs(x[0])))

• diff의 첫번째 원소가 가장 0에 가까운 합일 것이므로, 0번째 원소의 array 인덱스를 통해 array의 두 원소를 구한다.

 

 

풀이 코드

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

array.sort(key=abs)
diff = []
ans = 1e9

for i in range(1, n):
    temp = array[i] + array[i-1]
    diff.append((temp, i)) #i, i-1

diff.sort(key=lambda x: abs(x[0]))

index = diff[0][1]
ans = [array[index], array[index-1]]
print(*sorted(ans))