프로그래머스 3단계 "이중우선순위 큐"
문제
풀이
문제를 일반적인 리스트의 max 및 min을 사용해도 문제없이 풀수 있지만 문제 분류가 힙으로 되어있는 만큼 힙을 이용하여 문제를 풀었다.
파이썬의 heapq가 기본적으로 최소힙으로 이루어져 있어 최대값을 pop해주는데 있어 손을 좀 써야했다.
최소힙과 최대힙 두개를 만들어 동시에 조작하는 방법도 있지만 나는 heapq.nlargest를 이용하여 최대값을 찾고, 그 인덱스를 구해 pop하는 형식으로 코드를 구현하였다.
heapq.nlargest(a, b)
는 원하는 수(a)와 힙(b)을 인수로 받아 힙에서 가장 큰 수 a개를 리스트로 반환하는 함수이다.반대로
heapq.nsmallest(a, b)
는 가장 작은 수를 a개 찾는 함수이다.자세한건 여기를 참조하자.
Python 코드
import heapq
def solution(operations):
que = []
for x in operations:
oper, num = x.split()
num = int(num)
# 인덱스 오류날 시를 대비한 예외 처리
try:
if x == 'D 1':
# heapq의 nlargest를 이용하여 최대값을 구하고, 해당 인덱스 pop
print(heapq.nlargest(1, que)[0])
que.pop(que.index(heapq.nlargest(1, que)[0]))
elif x == 'D -1':
# heappop을 이용해 최소값 pop
heapq.heappop(que)
else:
# I일 경우 이중순위큐에 push
heapq.heappush(que, num)
except IndexError:
pass
if not que:
return [0, 0]
else:
return [max(que), min(que)]
Author And Source
이 문제에 관하여(프로그래머스 3단계 "이중우선순위 큐"), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kgpaper/프로그래머스-3단계-이중우선순위-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)