백준 - 11286. 절댓값 힙 (MJ)

#11286. 절댓값 힙

백준의 실버1티어 문제이다. 스터디에서 했던 힙 유형을 복습하기 위해 풀게 되었다.

참고로#11279. 최대 힙과 아주 유사하다.

📖Problems

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

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

출력

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

예제 입력 1

18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

예제 출력 1

-1
1
0
-1
-1
1
1
-2
2
0

🔍Institution

이 문제는 #11279. 최대 힙, #1927. 최소 힙 문제처럼 priority queue를 사용하면 된다. 이는 python에서 heapq모듈을 통해 구현한다.

🔍Concepts

• 힙 자료구조에 대해서는 최소힙, 최대 힙에서 정리해놓았기 때문에 간략하게만 살펴보겠다.
• Heap : Priority Queue와 같이 우선 순위가 존재하는 자료구조
  • 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전이진트리
  • Max Heap, Min Heap
• Heap을 사용하는 이유
  • 배열에서 최대 최소 값을 찾으려면 O(n) 이 걸리는데 비해 Heap은 O(log n)으로 성능이 더 좋다.
  • 배열에서 데이터의 최대, 최소 값을 찾기 위해 사용한다

파이썬에서 Heap 기능 사용하기

#1. module import
import heapq 

# 2. 최소 힙 생성
heap = []

# 3. 힙에 원소 추가 : `heappush(list, item)`
from heapq import heappush

heappush(heap, 4)
heappush(heap, 1)
heappush(heap, 7)
heappush(heap, 3)
print(heap)
# 결과 : [1,3, 7, 4]
# 시간복잡도 : O(log(n))

#4. 힙에서 원소 삭제 : `heappop(list)`
from heapq import heappop

print(heappop(heap))
print(heap)
'''
1
[3, 4, 7]
'''

#5.기존리스트를 힙으로 변환 : 이미 원소가 들어 있는 경우 → heapify()
from heapq import heapify

heap = [4, 1, 7, 3, 8, 5]
heapify(heap)
print(heap)
# 결과 :[1, 3, 5, 4, 8, 7]

🔍Approach

🚩My submission

조건

• 0 : 배열에서 ‘절댓값이’ 가장 작은 값 출력하고 그 값을 배열에서 제거 (heappop())
  • 만약 절댓값이 가장 작은 값이 여러 개인 경우 → 가장 작은 수를 출력하고 배열에서 제거
• 다른 숫자 : 배열에 push (heappush())

#11279최대힙, #1927최소힙에 다뤘던 힙 문제와 똑같다.

다만 heap을 tuple로 구성했을 때 맨 앞 숫자만 가지고 정렬하므로 앞은 abs(절대값) 내장 함수를 써주고 두 번째는 원래 수를 써줌으로써 절댓값 정렬을 할 수 있게 한다.

🚩Flow

1. 연산 개수 n을 입력받는다. heap리스트를 만든 후 heapify 시킨다.
2. 정수 num을 입력받는다.
3. 만약 num이 0일 경우에는 heappop()을 수행한다. 이때 절댓값에 대해 정렬되어 있는 상태이기 때문에 우선순위는 볼 필요가 없으므로 인덱스 1에 있는 값을 취한다.
   1. 또한 이 과정에서 heap이 비어 있을 경우에는 0을 출력하도록 한다.
4. num이 0이 아닐 경우(0을 제외한 수)일 경우, heap에 push한다.
   1. push할 때 (우선순위, 값) 를 튜플 형식으로 함께 써준다. 즉, 앞에는 절대값, 뒤에는 원래 수를 써줌으로서 절댓값에 맞게 정렬을 할 수 있도록 한다.
5. for문을 n만큼 반복한다.

import heapq
import sys

n = int(sys.stdin.readline())
abs_heap = []

for _ in range(n):
    num = int(sys.stdin.readline())
    if num == 0:
        if abs_heap:
            print(heapq.heappop(abs_heap)[1])
        else:
            print(0)           
       
    else:
        heapq.heappush(abs_heap, (abs(num), num))

🚩Others submission

출처 : https://claude-u.tistory.com/154

import sys
import heapq

numbers = int(input())
heap = []

for _ in range(numbers):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, (abs(num), num))
    else:
        try:
            print(heapq.heappop(heap)[1])
        except:
            print(0)

출처 : https://velog.io/@highcho/Algorithm-baekjoon-11286

import sys, heapq

abs_heap = []
n = int(sys.stdin.readline())
for i in range(n):
	num = int(sys.stdin.readline())
	if num:
		heapq.heappush(abs_heap, (abs(num), num))
	else:
		if abs_heap:
			print(heapq.heappop(abs_heap)[1])
		else:
			print(0)

• 훨씬 더 보기 깔끔한 것 같다.

💡TIL

• 앞선 문제들, 특히 max heap부분의 tuple 우선순위를 이용해 푸는 문제였다.
• 생각보다 간단하였으나 이 아이디어를 떠올리는데 시간이 꽤 걸렸다.
• heap에서 절댓값을 통해 max값을 구하기 위해선, heap에 push할 때 튜플의 형태로 첫번째 인자는 abs(num)을 두 번째 인자는 원래 수인 num을 함께 heappush한다.