[BOJ:11286]절댓값 힙

문제

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

[

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

](https://www.acmicpc.net/problem/11286)

코드

import sys
from heapq import heapify, heappush, heappop

#sys.stdin = open("input.txt","rt")

n = int(sys.stdin.readline().rstrip())

heap = []

for _ in range(n):
    cmd = int(sys.stdin.readline().rstrip())

    if cmd == 0:
        if len(heap):
            print(heappop(heap)[1])
        else:
            print(0)
    else:
        heappush(heap, (abs(cmd),cmd))

문제해결방법

• 문제의 주어진 조건에 따라 코드를 구현했다. 파이썬에서 heaq 라이브러리를 이용하면 쉽게 풀 수 있는 문제이다.
• cmd == 0 일때는 heap에서 절대값이 가장작은 값을 출력하고, 0이아닐 때는 그 정수를 힙에 push하면 된다.
• 파이썬에서 heqp은 기본적으로 최소힙을 이루기 때문에 루트에 최소값이 오도록 그대로 사용하면 되고 주의할 점은 절대값이 작은 기준으로 넣어주고 출력할 때는 원래 값이 그대로 나오도록 해야한다. 그러므로 저장 할때 절대값 처리를 해준 값과 원래의 값을 같이 저장해주어야하는데, 이때 튜플로 heap에 저장해주면된다. 파이썬에서 heap에 튜플을 저장할 때 0번 인덱스를 기준으로 저장한다.
• 출력할 때는 1번 인덱스를 출력 해주면 된다.