[Python CT#5] 최대 힙

 

 

 

#5 최대 힙

 

 

Q. 최대 힙을 사용합니다. 표준입력값을 확인하여 알맞은 로직을 완성시켜주세요

 

 

 

 

 

정답 코드

 

import sys
import heapq

n = int(sys.stdin.readline())
heap = [] 

for i in range(n):
    x = int(sys.stdin.readline())
    if x == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, -x)

 

 

 

풀이 과정!

문제를 정리해보고 풀이 진행하겠습니다.

 

1. 표준입력값이 0이면 heap 배열에서 가장 큰 수를 출력하고 배열에서 제외시켜야합니다.

2. 만약 배열이 비어있는 상태에서 0이 표준입력값으로 들어오면 0을 출력하면 됩니다.

3. 표준입력값이 0이 아니라면 표준입력값을 배열에 추가하면 됩니다.

 

 

import sys를 통해 백준에서 input으로 주는 표준입력값을 받아올 수 있습니다.

import heapq를 통해 힙 자료구조 편집을 용이하게 할 수 있습니다.

 

표준입력값 첫번째 줄에 연산 횟수가 들어있기때문에 n 변수로 담아두고 반복문에서 사용해보겠습니다.

heap = [] 배열을 생성하고 초기는 빈값으로 지정해둡니다.

 

 

# for문 입장

 

표준입력값 첫번째 줄에 연산횟수가 들어있기 때문에 이를 담은 n으로 반복문의 진행횟수를 지정할 수 있습니다.

또한, 매 줄마다 표준입력값을 확인해야하기 때문에 x변수에 sys.stdin.readline()으로 값을 할당합니다.

 

 

 

 

# if문 입장

 

만약 x(표준입력값)가 0이라면?

그리고 heap 배열이 빈 배열이 아니라면?

 

heapq.heappop(heap)을 실행합니다. 파이썬 공식문서의 heappop 설명을 보겠습니다.

heapq.heappop(heap)
힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.

 

heap에서 가장 작은 항목을 팝하고 반환합니다. 저희가 필요한 로직입니다. 작은 항목을 큰 항목으로 변경하면 되겠죠?

 

위 코드처럼 print(-heapq.heappop(heap)) 마이너스(-)를 통해 반대의 값 즉, 큰 항목을 추출할 수 있습니다.

 

heapq 모듈은 기본적으로 최소힙만을 지원하기 때문에

 

우리가 원하는 최대힙을 구현하기 위해서는 각 요소에 마이너스(-)를 달아줘야합니다.

 

heapq.heappush(heap,-x)를 통해 최대힙을 구현할 수 있습니다.

 

heapq.heappush(heap, item)

힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.