Easy is Perfect

[백준] 11286번 절댓값 힙 _ 문제 풀이

  • melonicedlatte
  • Apr 14, 2021


1. 문제

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

2. 풀이

해당 문제는 heap을 이용하여 문제를 해결해야 합니다. heap에 (절대값, 원래값) 을 넣어서 정렬하게 되면, 절대값 순서대로 정렬하고 절대값이 동일한 경우에는 원래값 순서대로 정렬하게 됩니다.

2.1. 시간초과 코드

python 에서 input 을 그대로 이용하면 heap 을 이용하더라도 시간초과가 발생하게 됩니다. 아래의 코드는 pypy로 제출해도 통과하지 못합니다.

N = int(input())
arr = []
for _ in range(N):
    a, b = map(int, input().split())
    arr.append((b,a))
[print(x[1], x[0]) for x in sorted(arr)]

2.2. 통과 코드

python 에서 input 대신 sys 패키지에 있는 sys.stdin.readline 함수를 사용하면 훨씬 더 빠르게 문제를 해결할 수 있습니다. 저는 pypy 로 아래의 코드를 이용하여 제출하였습니다.

import sys
import heapq
N = int(input())
heap = []
for _ in range(N):
    this_in = int(sys.stdin.readline())
    if this_in == 0:
        if len(heap) == 0:
            print(0)
            continue
        print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap, (abs(this_in), this_in))



Search