[백준] 11286번 절댓값 힙 (feat. 자료 구조, 우선순위 큐)

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

 

문제 분석

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

절대값 힙은 다음과 같은 연산을 지원하는 자료구조다.
1. 배열에 정수 x(x != 0)을 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거
   만약, 절댓값이 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거

단, 프로그램은 처음에 비어있는 배열로 시작.

- 입력
첫째 줄에 연산의 개수 N(1 <= N <= 100,000)
다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어짐.
만약 x가 0이 아니라면 배열 x라는 값을 추가하는 연산이고,
x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거
x의 범위는 (-2^31 < X < 2^31)

- 출력
입력에서 0이 주어진 횟수만큼 출력한다.
만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는, 0을 출력 할 것.

 

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

시간제한이 굉장히 빡빡한 문제다.

우선순위 큐를 이용하면 되는 문제라고 판단했다.
파이썬의 우선순위 큐는 기본적으로 최소힙이다.
우선순위 큐로 사용할 힙을 heap = [] 이라고 정의했다고 가정하면,
그렇다면 입력받은 정수가 x라고 했을 때, heapq를 이용해서 [abs(x), x] 이 형태로 heapq.heappush(heap, [abs(x), x])를 하면,
abs(x)를 기준으로 최소힙으로 정렬될 것이다.
그러면, heapq.heappop(heap)을 하면,
abs(x)가 가장 작은 [abs(x), x] 데이터가 뽑힐 것이고 출력을 해야할 때는, x를 출력할 수 있을 것이다.

 

코드 작성

 

'''
절대값 힙은 다음과 같은 연산을 지원하는 자료구조다.
1. 배열에 정수 x(x != 0)을 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
   만약, 절댓값이 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

- 입력
첫째 줄에 연산의 개수 N(1 <= N <= 100,000)
다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어짐.
만약 x가 0이 아니라면 배열 x라는 값을 추가하는 연산이고,
x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거하는 경우이다.
x의 범위는 (-2^31 < X < 2^31)

- 출력
입력에서 0이 주어진 횟수만큼 출력한다.
만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는, 0을 출력 할 것.

i)
우선순위 큐를 이용하면 되는 문제라고 판단했다.
파이썬의 우선순위 큐는 기본적으로 최소힙이다.
우선순위 큐로 사용할 힙을 heap = [] 이라고 정의했다고 가정하면,
그렇다면 입력받은 정수가 x라고 했을 때, heapq를 이용해서 [abs(x), x] 이 형태로 heapq.heappush(heap, [abs(x), x])를 하면,
abs(x)를 기준으로 최소힙으로 정렬될 것이다.
그러면, heapq.heappop(heap)을 하면,
abs(x)가 가장 작은 [abs(x), x] 데이터가 뽑힐 것이고 출력을 해야할 때는, x를 출력할 수 있을 것이다.
'''
import heapq
import sys

# 연산의 개수
n = int(sys.stdin.readline())

# 우선순위 큐로 사용할 힙 선언
heap = []

for i in range(n):
    now = int(sys.stdin.readline())
    abs_now = abs(now)
    if now != 0:    # 주어진 x가 0이 아니면
        heapq.heappush(heap, [abs_now, now])
    elif now == 0:  # 주어진 x가 0이면
        if len(heap) != 0:  # 배열이 비어있지 않다면,
            tmp_pop = heapq.heappop(heap)   # abs(x)가 가장 작은 값을 꺼내서
            print(tmp_pop[1])   # x를 출력
        else:   # 배열이 비어있으면,
            print(0)    # 0 추력

※ 우선순위큐의 개념을 알고, heapq를 잘 사용할 수 있으면 쉽게 풀 수 있는 문제다. 파이썬의 heapq는 기본적으로 최소힙이고,
만약 데이터를 [a, b]의 형태로 heappush를 하면 정렬 기준은 a이다. 이것을 잘 알아야 한다.