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

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 자료구조 중 최대 힙을 이용하여 자연수를 배열에 넣거나 배열에서 가장 큰 값을 출력하고 값을 배열에서 제거하는 문제이다.

문제는 최대 힙 자료구조를 구현해서 해결해야 하는데, 최대 힙 자료구조는 우선순위 큐 자료구조를 활용해 구현한다.

우선순위 큐 자료구조를 활용해 값을 넣고 제거하는데, 기본 우선순위 큐는 오름차순으로 값이 정렬되어 값을 가져오면 저장되어 있는 값들 중 가장 작은 값을 가져오게 된다.

하지만 해당 문제에서는 값을 가져올 때 가장 큰 값을 가져와야 하므로 우선순위 큐가 내림차순으로 정렬되어야 한다.

하여 우선순위 큐에 값을 추가할 때 (기준, 값)과 같이 튜플 형태로 값을 추가한다.

이때 기준은 값을 음수로 바꾸어 (-값, 값) 형태로 우선순위 큐에 값을 추가하여 -값이 큰 순서대로 튜플을 오름차순 정렬하여 실제 값은 내림차순으로 정렬되도록 구현한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 우선순위 큐 자료구조를 구현하기 위해 queue 모듈에서 PriorityQueue 함수를 불러온다. from queue import PriorityQueue
3. 우선순위 큐 자료구조를 구현한다. queue = PriorityQueue()
4. 입력할 연산의 개수를 입력받는다. N = int(sys.stdin.readline())
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()[1])
   3. 반면에 값이 0이 아닐 경우 (-값, 값) 형태로 우선순위 큐에 추가한다. else: queue.put((-x, x))

3. 소스코드

import sys
from queue import PriorityQueue

queue = PriorityQueue()

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

    if (x == 0):
        if (queue.empty()):
            print(0)
        else:
            print(queue.get()[1])
    else:
        queue.put((-x, x))