[Algorithm] 백준 11286 - 절댓값 힙 in Python(파이썬)

💡 백준 11286:

절댓값 힙 기본 구조 활용

🌱 코드 in Python

알고리즘: ABS Heap

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)

이번 문제도 역시 heapq 모듈을 활용하여 풀었다
이번에는 단순히 최소, 최대가 아닌 절댓값이 작은 순이면서 동시에 절대값이 같을 경우 주어진 숫자를 우선적으로 출력해야 한다

나는 이 문제를 튜플을 이용해서 풀었는데,
튜플의 경우 (a, b)와 같은 형태로 배열이 존재할 때 a값을 먼저 비교하고 b값을 비교한다

튜플이 아닐 경우, 최소/최대 힙 2가지를 만들어 비교하는 방법도 있다

import sys, heapq

min_heap = []
max_heap = []
n = int(sys.stdin.readline())
for i in range(n):
	num = int(sys.stdin.readline())
	if num > 0: # 양수일 때 최소 힙
		heapq.heappush(min_heap, num) 
	elif num < 0: # 음수일 때 최대 힙
		heapq.heappush(max_heap, -num) 
	else:
		if min_heap: # 최소 힙에 값이 존재하고
			if max_heap: # 맥스 힙에도 값이 존재할 때
				if min_heap[0] < max_heap[0]: # 최소 힙이 더 작은 경우에는
					print(heapq.heappop(min_heap)) # 최소 힙 출력
				else: # 최대 힙이 더 작은 경우에는
					print(-heapq.heappop(max_heap)) # 최대 힙 * -1 출력
			else: # 최소 힙만 존재할 때 
				print(heapq.heappop(min_heap)) # 최소 힙 출력
		elif max_heap: # 최대 힙만 존재할 때
			print(-heapq.heappop(max_heap)) # 최대 힙 출력
		else: # 둘 다 존재하지 않을 때
			print(0)

최소 힙에는 양수를, 최대 힙에는 음수를 넣어 놓고
최소 힙과 최대 힙 둘 다 값이 존재할 때 절대값을 비교후 적절한 값을 출력하고
둘 중 하나만 존재할 땐 각자의 최솟값, 없을 땐 0을 출력하도록 하면 된다

🧠 기억하자

1. -heapq.heappop(max_heap, -num 처럼 굳이 * -1이라고 적지 않아도 같은 연산이 된다..!

2. 절댓값은 abs(num) 함수를 이용하여 쉽게 구할 수 있다

백준 11286 바로가기