[백준] 11286 - 절대값 힙 (Python)

문제 출처 :

www.acmicpc.net/problem/11286

11286번: 절댓값 힙

문제 풀이:

• 기본 라이브러리에 있는 heap 모듈을 사용했다.
• abs_h에는 절대값만 넣었다. 이건 최소힙으로 사용된다.
• h_dict은 dict 형태로 key값에는 주어진 값의 절대값을 넣고 , value에는 값 자체를 넣는다. value에 넣은 다음엔 해당 key값의 value들만 sort한다.
• 이후 문제에 주어진 대로 연산을 진행한다.
  • 0이 아닌 값이 들어오면
    • abs_h에는 절대값으로 해당값을 넣어준다.
    • h_dict에도 해당 값이 키에 있는지 확인하고 키값에도 없으면 새로 만들어서 넣어주고 키값이 존재하면 존재하는 키값의 벨류(list)에 넣어준다.
    • 그뒤 h_dict의 키값 벨류(list)를 정렬한다.
  • 0이 들어오면
    • abs_h의 길이를 체크해서 0이면 heap이 비어있는 것이니 문제에서 시킨대로 0을 출력하낟.
    • 길이가 0이 아니면 최소힙으로 제거해야하는 값을 찾아내고 h_dict의 key으로 준뒤 가장 앞에 있는 값을 pop으로 제거한다.(이미 정렬했기 때문에 가장 앞에 있는 값만 뽑아도 무방하다.)
• cf) sys로 입력에 대한 조치를 하지 않으면 시간초과가 뜬다.

 

import heapq
import sys

input=sys.stdin.readline

abs_h = []
h_dict ={}

n=int(input())

for i in range(n):
    #print(abs_h,h_dict)
    o = int(input())
    if(o!=0):
        heapq.heappush(abs_h,abs(o))
        if(abs(o) not in h_dict.keys()):
            h_dict[abs(o)]=[o]
        else:
            h_dict[abs(o)].append(o)
        h_dict[abs(o)].sort()
    else:
        if(len(abs_h)==0):
            print(0)
        else:
            temp_val = heapq.heappop(abs_h)
            if(len(h_dict[temp_val])!=0):
                print(h_dict[temp_val][0])
                h_dict[temp_val].pop(0)
            else:
                print(0)