이중우선수위큐
시간 제한 : 10초
학습 키워드 : 힙,
문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어 수신 탑(높이)
I 숫자 큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
제한사항
operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
operations의 원소는 큐가 수행할 연산을 나타냅니다.
원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
풀이
통과 코드 1/
import heapq
def select_operation(oper: str) -> int:
if oper[0] == "I":
return 1
elif oper[-1] == "1" and oper[-2] == "-":
return 2
else:
return 3
def solution(operations):
min_heap = []
for oper in operations:
operation = select_operation(oper)
if operation == 1:
_, num = oper.split()
heapq.heappush(min_heap, int(num))
elif operation == 2:
if min_heap:
heapq.heappop(min_heap)
elif operation == 3:
if min_heap:
min_heap.pop()
min_heap.sort()
return [min_heap[-1],min_heap[0]] if min_heap else [0,0]
통과 코드는 매우 간단하지만 문제의 조건에 맞는 테스트 케이스가 더 있다면 통과하지 못하는 경우가 생긴다. 힙은 최소값을 보장하는 이진 트리 구조이기 때문에 마지막 값이 반드시 최댓값이라는 보장이 없다. 가령, 힙에 3,1,5,4,3의 순서로 들어간다면 1,3,5,4,3의 상태로 최댓값이 끝에 위치하지 않게 된다.
통과코드 2(보완)/
import heapq
def select_operation(oper: str) -> int:
if oper[0] == "I":
return 1
elif oper[-1] == "1" and oper[-2] == "-":
return 2
else:
return 3
def solution(operations):
min_heap = []
for oper in operations:
operation = select_operation(oper)
if operation == 1:
_, num = oper.split()
heapq.heappush(min_heap, int(num))
elif operation == 2:
if min_heap:
heapq.heappop(min_heap)
elif operation == 3:
if min_heap:
max_value = max(min_heap)
min_heap.remove(max_value)
heapq.heapify(min_heap)
min_heap.sort()
return [min_heap[-1],min_heap[0]] if min_heap else [0,0]
이 코드는 최댓값을 찾아 해당하는 최댓값을 없애준다.
코멘트
힙 자료구조에 대해서 배울 수 있는 좋은 기회였다. 문제의 핵심은 힙 자료구조는 정렬을 보장하지 않는다는 점이다. 최소 힙의 경우 루트노드가 항상 최솟값임을 보장하지만 그 반대는 성립하지 않는다. 그 반대가 되는 것이 채점 마지막 테스트케이스 6번이다. 따라서 통과코드 1번의 마지막에 sort를 해줬다. 다만, 이 경우에는 3,1,5,4,3,2의 순서로 들어갔을 경우에 최댓값을 제대로 빼주지 못하는 단점이 존재한다. 후에 통과 코드3으로 문제 이름에 맞게 이중힙 코드를 추가하겠다.
