문제 제목, 난이도
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 합니다.
체크리스트
우선순위 큐
자료구조 직접 구현하는 연습을 반복해서 하자
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ / Python] 14500번 : 테트로미노 (0) | 2021.05.14 |
---|---|
[BOJ / Python] 10026번 : 적록색약 (0) | 2021.05.11 |
[BOJ / Python] 1107번 : 리모컨 (0) | 2021.05.07 |
[BOJ / Python] 16928번 : 뱀과 사다리 게임 (0) | 2021.05.01 |