[백준] 11286번: 절댓값 힙 (sol.3)

풀이시간: 40분 (런타임 오류)

1. 나의 풀이

import heapq as hq

pq = []
minus_c = {}

T = int(input())

for _ in range(T):
    num = int(input())
    if num < 0:
        hq.heappush(pq, -num)
        if -num in minus_c:
            minus_c[-num] += 1
        else:
            minus_c[-num] = 1
    elif num > 0:
        hq.heappush(pq, num)
    else:
        if len(pq) > 0:
            root_node = hq.heappop(pq)
            if minus_c[root_node] > 0:
                print(-root_node)
                minus_c[root_node] -= 1
            else:
                print(root_node)
        else:
            print(0)

• 입력값들에서 최솟값을 출력해야함으로 힙(우선순위 큐)을 사용
• 절댓값에 대한 정보를 저장하는 방법이 떠오르지 않아 숫자별로 음수 갯수를 맵을 사용하여 저장하기로 함
• 최솟값 출력시 음수 갯수에 대한 정보가 0이 아니면 -을 붙여 출력하도록 구현

2. 또다른 풀이

1st

import sys 
import heapq as hq

input = sys.stdin.readline
pq = []

for _ in range(int(input())):
    x = int(input())
    if x:
        hq.heappush(pq, (abs(x), x))
    else:
        print(hq.heappop(pq)[1] if pq else 0)

• 파이썬은 비교적 느려서 빠른 입출력을 위해 사용: input = sys.stdin.readline
• 튜플로 된 배열을 정렬할 때, 첫번째 요소 기준으로 정렬이 되고 두번재 요소 기준으로 또다시 정렬된다.

2nd

import sys
import heapq as hq

input = sys.stdin.readline

min_heap = [] # 양수
max_heap = [] # 음수

for _ in range(int(input())):
    x = int(input())
    if x:
        if x > 0:
            hq.heappush(min_heap, x)
        else:
            hq.heappush(max_heap, -x)
    else:
        if min_heap:
            if max_heap:
                if min_heap[0] < abs(-max_heap[0]):
                    print(hq.heappop(min_heap))
                else:
                    print(-hq.heappop(max_heap))
            else:
                print(hq.heappop(min_heap))
        else:
            if max_heap:
                print(-hq.heappop(max_heap))
            else:
                print(0)

• 양수를 최소힙 음수를 최대힙에 따로 보관, 각각의 루트노드를 비교하여 출력 (비교시 4가지 상황이 나옴)
• 파이썬의 힙은 디폴트가 최소힙인데 최대힙으로 바꾸려면 들어갈 때 부호를 바꾸고 나올 때도 부호를 바꾸면 된다.

3. 보완할 것

• abs(): 절댓값 반환
• input = sys.stdin.readline # 빠른 입출력 지원
• 최대힙 구현 방법: 부호 바꾸기
• 튜플로 된 배열 정렬 로직
• if 문이 많아 질 것 같을 때 상황을 나누어 그려보자