[백준] 1927번 최소 힙

문제 내용

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

1927번: 최소 힙

풀이 과정

1,최초에는 deque를 이용해서 문제를 풀려고 하였지만 시간초과가 발생함.

2.이후 PriorityQueue(우선순위 큐)를 사용하여 문제를 풀어 제한시간 내로 풀이를 함.

풀이중 문제점

1.시간 초과 발생

2.PriorityQueue의 사용법 미숙

문제점 해결 과정

1.최초 풀이에서는 min()과 remove()를 사용해서 문제풀이를 진행하였음.

하지만 min()과 remove() 둘다 시간복잡도가 O(n)이어서 시간초과가 발생함.

이를 해결하기 위해 사전에 정렬을 시켜주는 PriorityQueue를 사용하기로함.

 

2. PriorityQueue에 대해 학습을 진행한후 풀이 진행.

=> 차후  PriorityQueue관련 포스트 작성으로 학습 예정

해결 코드

import sys
from queue import PriorityQueue
 
sys_input=sys.stdin.readline
 
q=PriorityQueue() #정렬을 위한 PriorityQueue
n=int(sys_input().rstrip())
 
for _ in range(n):
    a=int(sys_input().rstrip())
 
    if a==0:
        if q.qsize()==0:
            print(0)
        else:
            print(q.get())
    else:
        q.put(a)
 

주요 개념 

• 우선순위 큐(Priority Queue)
• 정렬(sort)