BOJ_11286 절댓값 힙

TOC {:toc}

이 글은 백준 온라인 저지의 11286번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.04.28

메모리	시간	코드 길이
37992 KB	168 ms	362 B

단계	시작 시각	끝난 시각
문제 이해	23:02:35	23:02:41
풀이 생각	23:02:50	23:03:02
코딩	23:03:14	23:15:18
디버깅	23:24:21	23:34:58

import sys
from heapq import *

H = []
input()
for n in map(int, sys.stdin):
    if n:
        heappush(H, (abs(n), n))
    else:
        if H:
            tmp = heappop(H)
            if H and tmp[0] == H[0][0] and tmp[1] > H[0][1]:
                print(heapreplace(H, tmp)[1])
            else:
                print(tmp[1])
        else:
            print(0)

아이디어 & 풀이

입력받은 값을 (절댓값, 입력값)의 튜플로 만들어 힙으로 관리한다. 절댓값으로 비교하고 입력값을 출력하면 된다.

디버그

replace 하는 조건을 만족시키지 않을 때 pop 했던 tmp를 출력하는 코드를 작성하지 않아서 틀렸다.
heappop(H)으로 원소를 pop하고 나서 바로 H의 원소에 접근하려고 해서 에러가 났다 (원소가 존재하지 않을 수 있어서).
- pop 한 다음에는 되도록 접근 전에 원소가 존재하는지 확인을 해주자.

피드백

튜플은 각 위치끼리 비교하기 때문에 heappush를 할 때 절댓값이 같으면 그다음의 n이 더 작은 튜플이 더 작은 값이 된다. 그러므로 굳이 둘을 비교해서 heapreplace 해주지 않고 heappop해도 n이 작은 튜플이 pop 된다. (풀이 2 참고)
- How does tuple comparison work in Python? by Stack overflow
- Expressions - Value Comparison by Python Documentation

참고 답안 1

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

n = int(input())
# 양수 값을 담을 heap과 음수 값을 담을 heap을 구분한다
P = []
M = []

for _ in range(n):
    x = int(input())
    # 받은 수가 0이면
    if x == 0:
        # P와 M이 존재하고
        if P and M:
            # 첫 원소를 비교했을 때 P가 더 작으면
            if P[0] < M[0]:
                # P를 pop 한 뒤 출력하고
                print(heappop(P))
            # 같거나 M이 더 작으면
            else:
                # M을 다시 부호를 바꿔 pop 한 뒤 출력한다.
                print(-heappop(M))
        # P만 존재하면
        elif P:
            # P를 pop 한 뒤 출력하고
            print(heappop(P))
        # M만 존재하면
        elif M:
            # M을 다시 부호를 바꿔 pop 한 뒤 출력한다.
            print(-heappop(M))
        else:
            print(0)
    # 0이 아니면
    else:
        # x가 양수일 경우
        if x > 0:
            # P에 push
            heappush(P, x)
        # 그 외의 경우
        else:
            # M에 부호를 바꿔 push 한다.
            heappush(M, -x)

참고 답안 2

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

H = []
for _ in range(int(input())):
    if (a := int(input())):
        heappush(H, (abs(a), a))
    else:
        print(heappop(H)[1] if H else 0)