[백준 11286] 절댓값 힙

11286번: 절댓값 힙

알고리즘 : 자료구조, 우선순위큐

난이도 : 실버Ⅰ

 

1. 문제요약

• '절댓값 힙'을 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 연산 pop을 지원하는 자료구조라고 하자. 다만 절댓값이 가장 작은 값이 여러개인 경우에는 가장 작은 수를 출력후 그 값을 배열에서 제거하고, 배열이 비었다면 0을 출력하기로 한다.
• 첫째 줄에 연산의 개수 N(100,000이하의 자연수)이 주어지고, 다음 N개의 줄에 연산에 대한 정보를 나타내는 정수 x가 주어진다. x가 0이 아니라면 배열에 x를 넣는 연산을 의미하고, x가 0이라면 위에서 정의한 연산 pop을 의미한다.
• 위와 같은 입력에 대한 출력을 보여주는 프로그램을 작성하면 된다.

2. 아이디어

• 이 문제는 양수에 대한 힙과 음수에 대한 힙을 따로 관리하는 방법으로 푸는게 정석인 것 같다.
• 그런데 모든 입력이 정수이기 때문에 음수를 소수로 관리하면 하나의 힙으로도 풀 수 있다.
• 예를들어 -13이 입력으로 들어오면 양수 13으로 변환시키고 여기서 0.5를 빼서 12.5로 만들수 있다. 이렇게 변환시키면 양수 13과 구별도 되면서 양수13과 함께 존재하는 경우 음수13을 먼저 출력할 수 있게 된다. 

3. 구현과정

• 힙을 사용하기 위해 heapq를 import하고, 빠른 입력처리를 위해 sys를 import하여 input을 처리해 준다.
• N을 입력으로 받고 N번 순회를 반복하면서 연산을 나타내는 정수를 tmp에 입력받는다.
• tmp가 양수라면 그대로 heap에 push해주면 된다.
• tmp가 음수라면 위의 변환과정을 거쳐 -tmp -0.5를 heap에 push해준다.
• tmp가 0이라면 이는 heappop을 하여 출력해주는 명령어이다.
  • heap에 원소가 존재하는 지 if문으로 확인한 뒤, heappop을 하여 heap에서 가장 작은 원소를 제거후 tmp2에 저장시킨다.
  • 만약 tmp2가 정수라면 양수이므로 그대로 출력해주고, 정수가 아니라면 음수이므로 다시 원래의 수로 변환시키는 작업을 거친 뒤 출력한다.
  • heap에 원소가 존재하지 않으면 0을 출력한다.

4. 파이썬 코드

import heapq
import sys

input = lambda: sys.stdin.readline().rstrip()
heap_abs = []
N = int(input())
for _ in range(N):
    tmp = int(input())
    if tmp > 0:
        heapq.heappush(heap_abs, tmp)
    elif tmp < 0:
        heapq.heappush(heap_abs, -tmp - 0.5)
    else:
        if heap_abs:
            tmp2 = heapq.heappop(heap_abs)
            print(tmp2 if isinstance(tmp2, int) else int(-tmp2 - 0.5))
        else:
            print(0)