[백준] 1927번 : 최소 힙 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 백준 11279번 : 최대 힙 문제와 유사하다.

이전 11279번 문제는 우선순위 큐에서 최댓값을 반환하도록 구현했다면 이번 문제는 최솟값을 반환하도록 구현해야 한다.

기본적으로 우선순위 큐 자료구조를 구현하면 값들이 오름차순으로 정렬되어 저장되므로 그냥 값을 추가하고 저장된 큐 자료구조에서 값을 가져오면 최솟값이 반환된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 우선순위 큐 자료구조를 구현하기 위해 queue 모듈에서 PriorityQueue 함수를 불러온다. from queue import PriorityQueue
3. 입력할 연산의 개수를 입력받는다. N = int(sys.stdin.readline())
4. 우선순위 큐 자료구조를 구현한다. queue = PriorityQueue()
5. 연산의 개수만큼 반복하며 for _ in range(N)
   1. 연산에 대한 정보를 입력받는다. x = int(sys.stdin.readline())
   2. 만약 값이 0일 경우 if (x == 0)
      1. 우선순위 큐 자료구조가 비어있으면 0을 출력하고 if (queue.empty()): print(0)
      2. 우선순위 큐 자료구조가 비어있지 않으면 제일 앞에 저장되어 있는 값을 가져와 출력한다. else: print(queue.get())
   3. 반면에 값이 0이 아닐 경우 값을 우선순위 큐에 추가한다. else: queue.put(x)

3. 소스코드

import sys
from queue import PriorityQueue

N = int(sys.stdin.readline())

queue = PriorityQueue()

for _ in range(N):
    x = int(sys.stdin.readline())

    if (x == 0):
        if (queue.empty()):
            print(0)
        else:
            print(queue.get())
    else:
        queue.put(x)