(Python)백준 코딩테스트 연습 - 최소 힙(1927)

1. 문제

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

2. 풀이

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

# n : 연산 개수
n = int(input())

# heap : 최소 힙 구조를 구현할 deque
heap = deque()

def popData(heap):
    popNum = heap.popleft()
    if len(heap) == 0:
        return popNum
    heap.appendleft(heap.pop())
    parentIdx = 1
    while True:
        childIdx1 = parentIdx * 2
        childIdx2 = parentIdx * 2 + 1
#         print("parentIdx :", parentIdx)
#         print("childIdx1 :", childIdx1)
#         print("childIdx2 :", childIdx2)
        if childIdx1 > len(heap):
#             print("childIdx1 >= len(heap)")
            break
        elif childIdx2 > len(heap):
#             print("childIdx2 >= len(heap)")
            childIdx = childIdx1
        else:
            if heap[childIdx1-1] < heap[childIdx2-1]:
                childIdx = childIdx1
            else:
                childIdx = childIdx2
        if heap[childIdx - 1] > heap[parentIdx - 1]:
            break
        else:
            heap[childIdx - 1], heap[parentIdx - 1] = heap[parentIdx - 1], heap[childIdx - 1]
            parentIdx = childIdx
    return popNum

def insertData(heap, insertData):
    heap.append(insertData)
    childIdx = len(heap)
    while True:
        if childIdx == 1:
            break
#         print("heap :", heap)
        parentIdx = childIdx // 2
#         print("childIdx :", childIdx)
#         print("parentIdx :", parentIdx)
        if heap[parentIdx-1] > heap[childIdx-1]:
            temp = heap[parentIdx-1]
            heap[parentIdx-1] = heap[childIdx-1]
            heap[childIdx-1] = temp
            childIdx = parentIdx
            continue
        else:
            break

# infoList : 연산 리스트
infoList = [int(input()) for i in range(n)]

for info in infoList:
#     print("info :", info) 
#     print("heap :", heap)
    if info == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(popData(heap))
    else:
        insertData(heap, info)
#     print("")

3. FeedBack

 - 이 문제는 문제의 제목에서 알 수 있듯이 최소 힙을 이용한 코드 풀이이다.

 이진 탐색을 이용하여 이진 트리의 깊이 만큼의 탐색 속도로 삽입, 출력을 진행하는 알고리즘으로 구현하였다.