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

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

11286번: 절댓값 힙

문제 설명

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

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

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

---

풀이 과정

이 문제는 두 가지 풀이방법을 이용하여 풀어보았습니다.

 

방법① 은 길이가 많이 간결한 방법으로

힙큐에 값을 넣을 때 (절대값, 원래값) 쌍으로 넣어줌으로써

절대값을 기준으로 정렬을 할 수 있게 하였습니다.

import sys
import heapq

n = int(input())
q = []

for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    if a != 0:
        heapq.heappush(q, (abs(a), a))
    else:
        if not q:
            print(0)
        else:
            print(heapq.heappop(q)[1])

 

방법 ② 은 첫 번째 방법보다 풀이가 다소 긴 감이 있지만

입력값이 양수인지 음수인지에 따라 서로 다른 공간에 저장을 하였습니다.

 

풀이 방법과 사고과정은 좀 더 복잡할 수 있지만,

간혹 우선순위큐에 익숙치 않은 분들은 요소를 두 개 이상 넣는 것을 모르고 계신 경우도 있어서

이 풀이를 참고하시면 될 것 같습니다!

import sys
import heapq

n = int(input())
q1 = [] # 음수를 넣을 큐
q2 = [] # 양수를 넣을 큐

for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    if a < 0:
        heapq.heappush(q1, -a) # 절대값이 작은게 앞에 와야 하므로
    elif a > 0:
        heapq.heappush(q2, a) # 양수이므로 그대로 최소힙으로 구현
    else:
        if not q1:
            if not q2:
                print(0)
            else:
                print(heapq.heappop(q2))
        elif not q2:
            print(-heapq.heappop(q1))

        else:
            tmp1 = -heapq.heappop(q1)
            tmp2 = heapq.heappop(q2)

            if abs(tmp1) > abs(tmp2):
                print(tmp2)
                heapq.heappush(q1, -tmp1)

            else:
                print(tmp1)
                heapq.heappush(q2, tmp2)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !