[파이썬] 백준 알고리즘 No.11286 절댓값 힙

https://acmicpc.net/problem/11286 

11286번: 절댓값 힙

 

절댓값과 일반값을 구분지어 저장하고, 

절댓값의 최소가 여러 개 있다면 그 일반값 중 최소를 출력하는 문제로

처음에는 deque와 람다 sorted 2중 정렬을 이용해 풀려고 했으나 시간 초과

 

 

시간 초과 코드

import sys
from collections import deque
input = sys.stdin.readline

a = deque()
for _ in range(int(input())):
    x = int(input())
    if x == 0:
        if len(a) == 0:
            print(0)
            continue
        a = deque(sorted(a, key=lambda q: (q[1], q[0])))
        print(a.popleft()[0])

    else:
        a.append((x, abs(x)))

 

 

 

 

10만이 넘는 배열 속에서 2^31의 최대 수를 정렬하려니 시간 초과.

파이썬 import heapq를 사용해서 절댓값을 뽑아주기로 했다.

 

import sys
import heapq
input = sys.stdin.readline

heap = []
for _ in range(int(input())):
    x = int(input())
    if x == 0:
        try:
            print(heapq.heappop(heap)[1])
        except:
            print(0)
        continue
    heapq.heappush(heap, (abs(x), x))

 

132176kb, 248ms로 해결