파이썬 알고리즘 171번 | [백준 1927번]최소힙

Yunny.Log ·2022년 6월 11일

Algorithm

목록 보기

174/318

171. 최소힙

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

heapq 를 활용한 힙 구현!

<내 풀이>

heapq.heappop(리스트)
heapq.heappush(리스트, 넣을 값)


import heapq
import sys

heap=[]
# minheap 에서 가장 작은 값은 이진트리의 루트에 위치
#k는 자식 원소 2k, 2k+1보다 작거나 같음 

n=int(sys.stdin.readline().strip())

# 가장 작은 애를 뒤에다가 넣기 
for i in range(n) :
    inp=int(sys.stdin.readline())
    if inp!=0:
        heapq.heappush(heap,inp)
        #heapq.heappush(넣을 리스트, 넣을 수)

    else : #0이라면 가장 작은 아이 remove
        if heap :
            print(heapq.heappop(heap))
        #heappop() 함수를 호출하여 원소를 
        # 삭제할 때마다 이진 트리의 재배치를 통해
        #  매번 새로운 최소값을 인덱스 0에
        else :
            print(0)

<내 틀렸던 풀이, 문제점>


import sys

n=int(sys.stdin.readline().strip())
lis = []

for i in range(n) :
    inp=int(sys.stdin.readline())
    if inp!=0:
        lis.append(inp)
    else :
        if lis :    
            print(min(lis))
            lis.remove(min(lis))
        else : print(0)