백준 절댓값 힙 - 11286 [파이썬, 자료 구조, 우선순위 큐]

11286번: 절댓값 힙

처음에 나는 이문제를 음수와 양수를 나눠서 정리는 방향으로 해결하였다.
하지만 나중에 풀이를 확인하던중 다른 좋은 해결법도 있어서 두가지 방법 모두 정리해보겠다.

#######################################################
import sys
import heapq
#######################################################
n = int(sys.stdin.readline())               # 받아올 정수의 개수
ml = []                                     # 음수를 저장할
pl = []                                     # 양수를 저장할

for i in range(n):                          # n만큼 돌린다.
    inp = int(sys.stdin.readline())         # 정수 받기
    if inp == 0:                            # 입력이 0이면 절대값 최소인 정수를 출력하거나 배열이 비어있으면 0출력
        if len(ml) == 0 and len(pl) == 0:   # 배열이 비어있다면
            print(0)                        # 0출력
        elif len(ml) == 0:                  # 음수 배열이 비어있다면
            print(heapq.heappop(pl))        # 양수 배열에서 pop
        elif len(pl) == 0:                  # 양수 배열이 비어있다면
            print(-(heapq.heappop(ml)))     # 음수 배열에서 pop하면서 -를 붙여준다.
        else:                               # 두 배열다 숫자가 있다면
            if ml[0] <= pl[0]:              # 두 배열을 비교하여
                print(-(heapq.heappop(ml))) # 작은 배열에서 출력
            elif ml > pl:                   # 두 배열을 비교하여
                print(heapq.heappop(pl))    # 작은 배열에서 출력
    elif inp > 0:                           # 입력값이 양수다
        heapq.heappush(pl, inp)             # 양수 배열에 push
    elif inp < 0:                           # 입력값이 음수다
        heapq.heappush(ml, -(inp))          # 음수를 -곱하고 배열에 정렬되도록 push

두번째 방법은 리스트에 push할 때 (절대값, 정수) 쌍으로 넣어주는 것이다. heap은 한쌍중 앞의 원소로만 정렬을 하기 때문에 자동으로 절대값으로 정렬이 된다.

#######################################################
import sys
import heapq
#######################################################
n = int(sys.stdin.readline())               # 받아올 정수의 개수
ab = []

for i in range(n):                          # n만큼 돌린다.
    inp = int(sys.stdin.readline())         # 정수 받기
    
    if inp != 0:                            # inp이 0이라면
        heapq.heappush(ab, (abs(inp), inp)) # (입력의 절대값, 입력) 쌍으로 heappush를 한다.
    else:                                   # inp이 다른 정수라면
        if len(ab) == 0:                    # ab의 길이가 0이면
            print(0)                        # 0출력
        else:                               # ab에 정수가 들어있으면
            print(heapq.heappop(ab)[1])     # 정수 출력