문제 링크

이 문제는 한 번에 풀이하지 못했다. heapq 모듈을 Import 해서 풀이해야겠다는 생각은 곧바로 들었지만 heappop() 메서드를 실행했을 때 절대값이 작은 값을 추출하도록 조건을 설정하는 것에서 헤맸다.

알고보니 조건을 설정하는 것이 아니라 heapq에 push할 때, 튜플 형태로 (abs(x), x) 이렇게 절대값과 원본값을 묶어서 저장해두었다가 결과를 저장하는 배열에는 index를 1로 잡아서 저장하니 원하는 결과를 얻을 수 있었다.

또한 이 문제는 시간제한이 있기 때문에 빠른 입출력도 함께 구현해야 한다.

튜플이 배열에 들어갔을 때, 정렬 기준

일차적으로 튜플의 가장 앞에 위치한 값을 비교하고, 그 값이 같다면 두 번째 값을 비교한다.

이 문제에서는 이를 활용하여 튜플 첫 값에 ABS() 값을 두어 우선적으로 절대값을 sort 기준으로 삼게 만들었다.

나의 풀이

import sys
import heapq

N = int(sys.stdin.readline())

hq = []      
result = []  

for _ in range(1 ,N+1):
    x = int(sys.stdin.readline())
    if x == 0:
        if len(hq)==0:
            result.append(0)
        else:
            result.append(heapq.heappop(hq)[1])
    else:
        heapq.heappush(hq, (abs(x),x))


for i in result:
    print(i)

해설을 보고 깨달음

• 굳이 Result 배열을 만들어줄 필요가 없었음.

  출력을 한 번에 한다는 조건이 없어서 인지 다음과 같이 작성해도 괜찮았따.

import sys
import heapq

N = int(sys.stdin.readline())

hq = []      
result = []  

for _ in range(1 ,N+1):
    x = int(sys.stdin.readline())
    if x :
        heapq.heappush(hq, (abs(x), x))
    else:
        print(heapq.heappop(hq)[1] if hq else 0)

• 또 다른 풀이

  Min-heap 과 Max-heap을 각각 만들고 Min-heap 에는 양수만, Max-heap에는 음수만 넣어준다. 그리고 각각의 root 노드를 비교하고 더 작은 값을 꺼내어 print 하면 된다.

import sys
import heapq as hq

input = sys.stdin.readline

min_heap = [] #양수
max_heap = [] #음수

for _ in range(int(input())):
  x = int(input())
  if x:
    if x > 0:
      hq.heappush(min_heap, x)
    else:
      hq.heappush(max_heap, -x) # max_heap으로 구현하고자 부호를 반전 시키고 꺼낼때도 부호 반전
  else:
    if min_heap:
      if max_heap:
        if min_heap[0] < abs(-max_heap[0]):
          print(hq.heappop(min_heap))
        else:
          print(-hq.heappop(max_heap))
      else:
        print(hq.heappop(min_heap))
    else:
      if max_heap:
        print(-hq.heappop(max_heap))
      else:
        print(0)