07
10

문제 제목, 난이도

11286번 : 절댓값 힙, 실버1


문제 링크

 

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

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net


코드(Python)

import sys
import heapq

input = sys.stdin.readline

li1 = []
li2 = []

for _ in range(int(input())) :
    command = int(input())
    
    if command == 0 :
        if li1 or li2 :
            if li1 and li2 :
                if li1[0] == li2[0] :
                    print(-(heapq.heappop(li2)))
                elif li1[0] < li2[0] :
                    print(heapq.heappop(li1))
                elif li1[0] > li2[0] :
                    print(-(heapq.heappop(li2)))
            elif li1 == [] :
                print(-(heapq.heappop(li2)))
            elif li2 == [] :
                print(heapq.heappop(li1))
        else : 
            print(0)
    else :
        if command < 0 :
            heapq.heappush(li2, -command)
        else :
            heapq.heappush(li1, command)

풀이

파이썬에서 제공하는 heapq 를 사용합니다.

heapq는 최소 힙을 지원하는 모듈이므로 음수를 집어넣을 때는 -로 넣되, 출력할 때 -를 붙여서 출력하도록 합니다.

문제에서는 절댓값 힙을 요구했습니다. 따라서 양수를 넣는 큐, 음수를 넣는 큐를 각각 만든 뒤, 0번째 인덱스 값을 비교해서 해당하는 값을 pop 해주는 방식입니다. 반대편 큐가 비어있을 때 인덱스 오류를 피하기 위해 비어있지 않은 큐에서 pop 합니다.


체크리스트

우선순위 큐

자료구조 직접 구현하는 연습을 반복해서 하자

COMMENT