[백준] 11279번 최대 힙 (feat. 자료 구조, 우선순위 큐)

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

 

문제 분석

• 첫 번째 단계(문제 요약 및 조건 파악)

자료구조 중 최대 힙이 있다.
최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성할 것.
1. 배열에 자연수 X를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작한다.

- 입력
첫째 줄에 연산의 개수 N (1 <= N <= 100,000)이 주어진다.
다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다
만약 x가 자연수라면, 배열에 x라는 값을 넣는 연산,
만약 x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 연산.
입력되는 자연수는 2^31 보다 작다.

- 출력
입력에서 0이 주어진 회수만큼 답을 출력.
만약 배열이 비어있는 경우인데 가장 큰 값을 출력하라고 하면 0을 출력 할 것.

 

• 두 번째 단계(문제 핵심 파악)

입력받은 값 x가 자연수면,
배열에 입력받은 x를 추가한다.

입력받은 값 x가 0이면,
우선순위 큐를 이용하여 배열의 가장 큰 값을 꺼내서 출력하고,
그 값을 배열에서 제거해야 한다.

그런데, 파이썬의 우선순위 큐는 최소힙이기 때문에,
최대힙으로 이용하기 위해서는 값들에 -부호를 붙여주어서 사용해야한다.

0이 주어진 횟수만큼 답을 출력해야 하는데,
만약에 0이 주어진 상태에서 3이 추출되었으면, 3을 출력하라는 의미다.
또한
만약에 0이 주어진 상태인데 배열이 비어있는 상태면 0을 출력하라는 의미다.

이 로직을 코드로 구현해보자.

 

코드 작성

 

'''
- 문제 요약
자료구조 중 최대 힙이 있다.
최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성할 것.
1. 배열에 자연수 X를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작한다.

- 입력
첫째 줄에 연산의 개수 N (1 <= N <= 100,000)이 주어진다.
다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다
만약 x가 자연수라면, 배열에 x라는 값을 넣는 연산,
만약 x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 연산.
입력되는 자연수는 2^31 보다 작다.

- 출력
입력에서 0이 주어진 회수만큼 답을 출력.
만약 배열이 비어있는 경우인데 가장 큰 값을 출력하라고 하면 0을 출력 할 것.

i)
입력받은 값 x가 자연수면,
배열에 입력받은 x를 추가한다.

입력받은 값 x가 0이면,
우선순위 큐를 이용하여 배열의 가장 큰 값을 꺼내서 출력하고,
그 값을 배열에서 제거해야 한다.

그런데, 파이썬의 우선순위 큐는 최소힙이기 때문에,
최대힙으로 이용하기 위해서는 값들에 -부호를 붙여주어서 사용해야한다.

0이 주어진 횟수만큼 답을 출력해야 하는데,
만약에 0이 주어진 상태에서 3이 추출되었으면, 3을 출력하라는 의미다.
또한
만약에 0이 주어진 상태인데 배열이 비어있는 상태면 0을 출력하라는 의미다.

이 로직을 코드로 구현해보자.
'''

# 연산의 개수 n
import heapq
import sys

n = int(sys.stdin.readline())
heap = []   # 최대힙으로 사용할 힙 선언

for i in range(n):
    now = int(sys.stdin.readline())
    if now != 0:    # 입력받은 수가 0이아닌 자연수면
        heapq.heappush(heap, -now)  # 힙에 추가한다. 단 최대힙으로 작동되도록 -부호를 붙여서 추가
    else:   # 입력받은 수가 0이면
        if len(heap) != 0:  # 만약 배열이 비어있지 않다면, heap에서 가장 큰 값을 꺼내서 출력하고, 그 값은 배열에서 제거
            result = heapq.heappop(heap)
            print(-result)  # 최대힙이 되도록 -부호를 붙였었으므로 다시 -부호를 붙여서 출력
        else: # 만약 배열이 비어있다면,
            print(0) # 0을 출력

※ 이 문제는 시간제한이 빡빡하다. 입력도 sys로 받아야 하고, 입력받은 수들 중, 가장 큰 값을 뽑을 때, 힙 자료구조를 이용해야 한다.
힙 자료구조, 우선순위 큐에 대해 잘 이해하고 있으면, 쉽게 해결 할 수 있는 문제다.