용액 풀이
풀기 위해 생각해야 할 것.
1. 두개의 용액 비교하기.
2. 첫번째 용액을 target 으로 설정해주고 for 문 돌려서 모든 용액 검사.
3. -target과 배열의 미드를 비교하는데,
타겟이 더 크면 오른쪽에 타겟과 일치하는 것이 있다는 것.
타겟이 더 작으면 왼쪽에 타겟과 일치하는 것이 있다는 것.
을 뜻하므로 해당 위치에서 재귀를 돌아줌.
-> 계속 재귀 돌리다보면, start=end 가 되어서 가장 -target 과 가까운 (즉 더해서 가장 0과 가까운) 숫자를 찾을 수 있음.
이 숫자를 리턴해주고, 이것을 함수 밖에서 처리해주는게 좋음(그래야 덜 복잡함.)
-> 이때 주의사항은, 이진탐색 후 나온 값이 -target과 일치하지 않는다면 그 위의 값이라는 것.
그러므로 그 값과 해당 값-1을 비교해주어야 한다.
-> 이진탐색 후 나온 값이 0 일 경우 -1 해주지 못하므로 pass해줌.
-> 추가로, arr[이진탐색후나온index값]==0일 경우 본인과 같은 값을 더해준게 0이 되어 가장 0과 가까운 값이 되므로 나온 index값과 현재 값이 같지 않을때만 a,b 에 넣을 수 있도록 조건을 넣어준다.
예)
-99 -10 2 5 80 98 103 일 때,
-99 와 다른 값들을 비교해주는데,
첫번째 시행 시 : 6//2=3 -> mid=3 ,99(-target)>5
두번째 시행 시 : start=4~6-> mid=5,99(-target)>98
세번째 시행 시 : start=6 end=6->mid=6,99(-target)<103
그러므로 해당 이진탐색 함수는 6 인덱스를 반환.
-> -target 보다 +1의 인덱스를 반환하여 위 인덱스와 -1인덱스를 둘 다 비교해주어야 함.
import sys
sys.setrecursionlimit(1000000000)
# 재귀함수 횟수제한을 늘려주는 것.
N = int(input())
liquid = list(map(int, sys.stdin.readline().split()))
# stdin.readline 이 input 보다 빠름.
liquid.sort()
k = 3000000000
a = 0
b = 0
def binary(arr, target, start, end): # target = - (-99)=99
if start >= end:
return start
mid = (start+end)//2
if arr[mid] < target: # 타겟이 mid보다 크다는것 -> 오른쪽에서 재귀.
return binary(arr, target, mid+1, end) # start = 1
else:
return binary(arr, target, start, mid)
for i in range(N):
bin = binary(liquid, -(liquid[i]), 0, N-1)
if k > abs(liquid[bin]+liquid[i]) and bin != i:
a = (liquid[i])
b = liquid[bin]
k = abs(a+b)
if bin == 0:
continue
if k > abs(liquid[bin-1]+liquid[i]) and bin-1 != i:
a = (liquid[i])
b = liquid[bin-1]
k = abs(a+b)
if a > b:
a, b = b, a
print(a, b)-> 투포인터로도 구할 수 있지만 투포인터가 더 느림.
++빅오 구하는법도 공부해보자.
