[Python3, 파이썬] 백준 11286번 절댓값 힙

일단 파이썬의 heapq 모듈은 min-heap이기 때문에 루트노드에 최소값이 위치하게 된다.

 

**튜플 정렬을 이용.

예를 들어 arr = [(3, 4), (3, 1), (8, 5), (3, 2), (8, 7)] 이 있으면

arr.sort() 했을 때 튜플들의 0번째 기준으로 오름차순으로 먼저 정렬한 다음 1번째 인덱스 기준으로 정렬한 다음 보여준다.

print(arr) >>> [(3, 1), (3, 2), (3, 4), (8, 5), (8, 7)] 이다.

 

(적용과 해결)

import heapq as hq, sys

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

이러한 특성을 이용하여 x를 입력받아서 heapq에 넣는데, 넣을 때 (abs(x), x)의 튜플 형태로 넣어준다.

이렇게 넣으면 테스트 케이스를 넣을 때

입력 => heapq에 들어갈 튜플형태

1 => (1, 1)

-1 => (1, -1)

0 => 현재 힙큐 상태 [(1, -1), (1, 1)] 이므로 heappop()으로 꺼내면 (1, -1)이 나오고 여기서 1번째 인덱스만 꺼내면 문제 조건을 만족시킬 수 있다.

 

중간의 1, 1, -1, -1, 2, -2를 입력 받으면 

[(1, -1), (1, -1), (1, 1), (1, 1), (2, -2), (2, 2)] 의 상태가 될 것이고 뒤의 0들을 입력받으면 앞의 것들부터 튀어나올 것이다.