본문 바로가기

카테고리 없음

[백준 2467번] 용액 (Python3)

import sys
input = sys.stdin.readline
import heapq

N = int(input())

sol = list(map(int,input().split()))

hq = []
for i in range(N):
  heapq.heappush(hq,(abs(sol[i]),sol[i]))

SUM = sys.maxsize
last = heapq.heappop(hq)[1]
while hq:
  now = heapq.heappop(hq)[1]
  if abs(last+now) < SUM:
    SUM = abs(last+now)
    result = sorted([last,now])
  last = now

print(result[0],result[1])

 

힙큐를 이용해서 구현하였다. 힙큐에 모든 데이터를 절댓값을 기준으로 튜플로 저장한 뒤, hq에서 뽑은 값과 이전 값의 합을 비교하며 결과를 출력한다.

 

참고로 처음에는 이 코드가 name error가 났었는데, SUM 초기값을 10**9로 둔게 실수였다. 용액이 10**9가 최댓값인데, 합은 그거보다 더 클 수가 있었기 때문이다. sys.maxsize로 바꿔주자 에러가 나지 않았다.

 

다른 사람들 풀이를 보니 heapq를 이용해 구현한 사람들은 거의 없어보였다. 투 포인터와 이진탐색 알고리즘이라는걸 이용한 사람들이 많아보였는데, 둘다 처음듣는 알고리즘이었기에 공부할 필요가 있어보인다.

 

 

오늘의 교훈) 투포인터 알고리즘과 이진탐색 알고리즘을 공부하자