💻 백준 11286: 절댓값 힙

문제 소개 🧐

배열에 정수 x를 넣거나, 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 제거하는 문제입니다. 절댓값이 같은 수가 여러 개일 경우에는, 가장 작은 수를 출력해야 합니다.

입력 📝

  • 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어집니다.
  • 이어서 N개의 줄에 정수 x가 주어집니다.
  • x가 0이 아니라면 배열에 x를 추가하고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거합니다.

출력 📤

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

첫 번째 시도: 튜플을 활용한 정렬 🚀

Idea

이 문제는 절댓값을 기준으로 힙 정렬을 하되, 만약 절댓값이 같다면 실제 값이 더 작은 수를 우선적으로 출력해야 했다

heapq가 튜플(tuple)을 원소로 받을 경우, 튜플의 첫 번째 요소부터 순서대로 비교하며 정렬하는 특징을 활용하기로 했다

그래서 (abs(x), x) 형태의 튜플을 힙에 저장하는 아이디어를 떠올렸다

이렇게 하면 먼저 절댓값을 기준으로 최소 힙 정렬이 되고
절댓값이 같은 원소들 사이에서는 원래 값 x를 기준으로 다시 정렬될 것이라고 생각했다

이 방법으로 추가적인 조건 분기 없이 힙의 정렬 기준을 효과적으로 제어할 수 있었다

Code

import heapq
import sys

input = sys.stdin.read
data = list(map(int, input().split()))

heap = []
results = []
n_index = 0
N = data[n_index]
n_index += 1

for _ in range(N):
    x = data[n_index]
    n_index += 1
    if x == 0:
        if heap:
            results.append(str(heapq.heappop(heap)[1]))
        else:
            results.append("0")
    else:
        heapq.heappush(heap, (abs(x), x))

print("
".join(results))

Result

  • 성공! 🎉
  • 튜플의 특성을 활용해 heapq의 정렬 기준을 커스텀하는 방법을 명확히 이해할 수 있었다

개선할 부분 🤔

  • 튜플을 이용해 heapq의 정렬 우선순위를 커스텀하는 방법을 배울 수 있었다
  • 복잡한 조건이 주어졌을 때, 자료구조의 특성을 어떻게 창의적으로 활용할 수 있는지 고민해보는 계기가 되었다
  • 앞으로 비슷한 다중 조건 정렬 문제가 나오면 이 아이디어를 적극적으로 활용해야겠다