🔍 Problem

11279 최대힙

이 문제는 처음에 입력 받은 수 N개 만큼 입력이 들어온다. 그리고 그 입력을 처리하는 경우는 두가지로 나뉜다. 첫 번째는 자연수인경우다. 이 경우에는 큐안에 그 입력값을 넣으면 된다. 두 번째는 “0”인 경우이다. 이 경우에는 큐 안의 가장 큰 값을 출력하는데, 만약 큐가 비었을 경우에는 0을 출력하면 된다. 이 문제는 얼핏보면 쉬워보이지만 시간제한이 1초이다. 아마도 빠른 자료구조를 사용하여 구현해야할 것 같다. 그리고 그것은 우선순위 큐지 않을까?

---

📃 Input&Output

---

📒 해결과정

가. 안에 있는 값들에서 큰 순서대로 하나씩 빼와야된다.

나. 1초안에 해야하므로 시간이 빠른 우선순위 큐를 사용한다.

다. 하지만 우선순위 큐는 작은 값을 우선순위가 높다고 판단해서 그것을 먼저 가져온다.

라. 그렇다면 -1을 곱해서 더 큰 값일 수록 더 작게만들어서 우선순위를 높게 만든다.

마. 그리고 출력할 때 다시. 1을 곱해서 출력

---

💻 Code

import sys
import os
from queue import PriorityQueue

# input=sys.stdin=open(os.getcwd()+"//6_Prior_Que//11279//input.txt")
input=sys.stdin

N=int(input.readline())

que=PriorityQueue()

for _ in range(N):
    num=int(input.readline())
    
    if num==0:
        if que.empty():
            print(0)
        else:
            print(-1*que.get())
    
    else:
        que.put(num*-1)

---

🤔 느낀점

우선순위 큐를 힙으로 나중에 구현해야겠지만 파이썬의 편한 PriorityQuere라이브러리 때문에 손쉽게 해결할 수 있었다.