99클럽 코테 스터디 5일차 TIL + 이분검색

오늘의 문제

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

문제 이해

-1,000,000,000 ~ 1,000,000,000 의 값을 가진 용액이 있음.
2개의 용액을 선택해 합쳐서 0에 가장 가까운 두 용액을 찾는 것이 목적

-입력
5
-2 4 -99 -1 98

-출력
-99 98

문제 접근

• 이분 탐색을 사용해야한다고 생각한 이유
  1) 만약 모든 용액 쌍을 순열로 비교한다면, 가능한 모든 조합의 개수는 ((n)*(n-1)/2)으로,
  O(N^2)이 되게 된다.

sudo code

1. 입력 받은 용액리스트를 정렬.
2. 가장 작은 값과 가장 큰 값의 합 변수 지정
3. answer = 현재 2개의 용액 값을 저장할 리스트 지정
4. left 는 0, right는 (용액리스트의 길이)-1이 되게 된다.
   왜냐? >> (용액리스트의 길이)로 하면 용액 리스트의 index를 벗어나게 된다.
5. left가 right를 넘지 않을 때까지 반복
   5-1. 만약, abs(리스트[left] + 리스트[right])가 answer보다 작으면, answer = abs(리스트[left] + 리스트[right])가 되고, final 은 리스트[left], 리스트[right]가 되게 된다.
   5-2. 만약, (리스트[left] + 리스트[right])가 0보다 크면?
   -> right를 왼쪽으로 한칸 이동 (0보다 크다는 것은, right의 값(+)이 더 크기 때문에 + 로 나온 거기 때문에 양의 수 중에 작은 값으로 변경 필요)
   5-3. 만약, (리스트[left] + 리스트[right])가 0보다 작으면?
   -> left를 오른쪽으로 한칸 이동
   (0보다 작다는 것은, left의 값(-)이 더 크기 때문에 -로 나온 것이고, 음의 수를 작은 값으로 변경)

실제 코드

cnt = int(input())
solution = list(map(int,input().split()))
start_point = 0
end_point = len(solution) -1
sorted_solution = sorted(solution)
final = [sorted_solution[start_point], sorted_solution[end_point]]
abs_sum = abs(sorted_solution[start_point] + sorted_solution[end_point])
while(start_point < end_point):
   sum_value = sorted_solution[start_point] + sorted_solution[end_point]
   if abs(sum_value) <= abs_sum:
       abs_sum = abs(sum_value)
       final = [sorted_solution[start_point], sorted_solution[end_point]]
   if sum_value < 0:
       start_point +=1
   else:
       end_point -=1
print(final[0], final[1])

느낀점

진짜 문제를 점점 꼬아진다는 걸 느낀다...
그래도 뭔가 이렇게도 문제가 나온다? 라는 걸 깨달았다.
지금 푼 문제가 완벽히 내 것이 아니기 때문에 복습, 또 복습을 해야할 것 같다.