[자료구조/힙] 백준 11286 절댓값 힙 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11286번: 절댓값 힙

 

 

 

2. 문제 풀이

 절댓값 힙을 구현하는 문제입니다. 절댓값이 작은 것부터 pop하며, 절댓값이 같을 경우에는 음수를 pop합니다.

 

2022.02.20 - [Algorithm] - [Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐

[Algorithm] 힙(heap), 최소/최대로 정렬하는 우선순위 큐

 

 

 

3. 코드

import sys
import heapq
input = sys.stdin.readline

N = int(input())
minusHeap = [] # 음수만 저장
plusHeap = [] # 양수만 저장

 음수를 저장할 heap과 양수를 저장할 heap를 따로 설계합니다.

 

 

for _ in range(N):
    x = int(input())
    # x가 음수일 때
    if x < 0:
        heapq.heappush(minusHeap, -x) #최대 힙과 비슷하게 마이너스 붙여서 저장

    # x가 양수일 때
    elif x > 0:
        heapq.heappush(plusHeap, x)

 x가 음수이면 최대 힙과 마찬가지로 마이너스를 붙여서 저장합니다. ( -[음수의 최솟값] = 양수의 최댓값 )

 x가 양수일 때에는 최솟값을 반환해야 하므로, 그대로 저장합니다.

 

 

# x가 0이고 둘 다 비어있지 않으면 비교 후 pop
elif minusHeap and plusHeap:
    if minusHeap[0] == plusHeap[0]: #둘의 절댓값이 같으면, minusHeap에서 pop
        print(-heapq.heappop(minusHeap))
    elif minusHeap[0] > plusHeap[0]:
        print(heapq.heappop(plusHeap))
    else:
        print(-heapq.heappop(minusHeap))

 절댓값이 같을 때에는 minusHeap에서 음수를 pop합니다.

 그 외에는 절댓값이 작은 힙에서 반환합니다.

 

 

# x가 0이고 minusHeap만 있을 때
elif minusHeap:
    print(-heapq.heappop(minusHeap))

# x가 0이고 plusHeap만 있을 때
elif plusHeap:
    print(heapq.heappop(plusHeap))

# x가 0이고 모두 비어있으면 0 출력
else:
    print(0)

 둘 중 한 개의 힙이 비었을 때에는, 남은 힙에서만 반환합니다.

 둘 다 비었을 때에는 0을 출력합니다.

 

 

<전체 코드>

import sys
import heapq
input = sys.stdin.readline

N = int(input())
minusHeap = [] # 음수만 저장
plusHeap = [] # 양수만 저장

for _ in range(N):
    x = int(input())
    # x가 음수일 때
    if x < 0:
        heapq.heappush(minusHeap, -x) #최대 힙과 비슷하게 마이너스 붙여서 저장

    # x가 양수일 때
    elif x > 0:
        heapq.heappush(plusHeap, x)

    # x가 0이고 둘 다 비어있지 않으면 비교 후 pop
    elif minusHeap and plusHeap:
        if minusHeap[0] == plusHeap[0]: #둘의 절댓값이 같으면, minusHeap에서 pop
            print(-heapq.heappop(minusHeap))
        elif minusHeap[0] > plusHeap[0]:
            print(heapq.heappop(plusHeap))
        else:
            print(-heapq.heappop(minusHeap))

    # x가 0이고 minusHeap만 있을 때
    elif minusHeap:
        print(-heapq.heappop(minusHeap))

    # x가 0이고 plusHeap만 있을 때
    elif plusHeap:
        print(heapq.heappop(plusHeap))

    # x가 0이고 모두 비어있으면 0 출력
    else:
        print(0)
    #print(minusHeap, plusHeap) 힙 동작 확인

 

 

cf) 튜플을 이용한 풀이

import sys
import heapq
input = sys.stdin.readline

N = int(input())
heap = []

for _ in range(N):
    x = int(input())
    if x != 0:
        heapq.heappush(heap, (abs(x), x)) # (절댓값, 숫자)로 저장
    elif heap: # 비어있지 않으면
        print(heapq.heappop(heap)[1])
    else: # 비어있으면
        print(0)

 맞은 사람 코드에서 튜플로 간단하게 구현한 코드가 있었습니다.

 (절댓값, 숫자) 튜플로 힙 구성하면, 저절로 절댓값 중 최소를 반환합니다.

 절댓값이 같을 경우, 두 번째 원소인 숫자가 작은 걸로 반환합니다.