문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42628
문제 접근(문제 분석 → 풀이 아이디어)
이중 우선순위 큐
파이썬의 heapq는 최소 힙으로 동작한다.
따라서 heapq을 이용해 최대값을 구하기 위해선 별도의 전처리로 최대힙을 구현해야한다.
# 최소값
heapq.heappop(리스트)
# 최대값
heap = list(map(lambda x : -1*x , heap)) # 음수로 리스트 변환하기
heapq.heapify(heap)
heapq.heappop(heap)
heap = list(map(lambda x : -1*x , heap)) # 변환한 음수 리스트를 다시 양수로 변환
3가지 명령문에 따른 우선순위 큐 함수 동작 조건
연산 종료 후 큐에 상태에 따른 출력 형태 :
큐가 비어 있음 [0,0]
비어 있지 않음 [최대값, 최솟값]
→ 큐에 1개 값만 존재하는 경우 , 최대값 = 최소값임으로 이를 고려해서 출력 형태를 잡아야 한다.
코드를 풀이할 때 적었던 플로우가 있나요?
문제에 주어진 이중우선순위 큐 함수를 정의한다.
[3가지 동작]
(1) 큐에 숫자 삽입하기 I 숫자 :
heapq.heappush(heap , int(num))
(2) 큐에서 최소값 삭제하기 (D -1 )
heapq.heapify(heap)
heapq.heappop(heap)
(3) 큐에서 최대값 삭제하기 (D 1)
` heap = list(map(lambda x : -1*x , heap))
heapq.heapify(heap)
heapq.heappop(heap)
heap = list(map(lambda x : -1*x , heap))
입력 명령문에 대해 반복문을 실행한다.
최종 큐의 상태에 따라 출력 형태를 변형한다.
case1. 큐에 요소가 2개 이상 존재하면-> 최대값 & 최소값 출력
case2. 큐가 비어 있으면 → [0,0
case3. 큐에 요소가 1개만 존재하면 → [값, 값]
"""
- 우선순위 큐 함수 조건
- l 숫자 : 큐에 해당 숫자 삽입
- D -1 : 큐에서 최소값 삭제(빈 큐면 무시 )
- D 1 : 큐에서 최대값 삭제
- 출력 : 연산 종료 후 큐가 비어 있음 [0,0] / 비어 있지 않음 [최대값, 최솟값]
-
"""
import heapq
def solution(operations):
answer = []
heap = []
def prior_queue(operate , heap) : # 입력 명령문 종류에 따라 3가지 동작 중 택 1을 적용한다.
action , num = operate.split()
# [0] (예외처리)빈 heap에 삭제 명령이면, 무시한다.
if not heap and action == "D":
return heap
# [1] 큐에 삽입하기
if action == "I" :
heapq.heappush(heap , int(num))
# [2] 최소값 삭제
elif action == "D" and num == "-1":
heapq.heapify(heap)
heapq.heappop(heap)
#[3] 최대값 삭제
elif action == 'D' and num == "1" :
heap = list(map(lambda x : -1*x , heap))
heapq.heapify(heap)
heapq.heappop(heap)
heap = list(map(lambda x : -1*x , heap))
return heap
#2. 입력 명령문에 대해 반복 동작하기
for o in operations :
heap=prior_queue(o , heap )
#3. 출력 형태 맞춰 변형하기
if len(heap) >=2 : # (1)안 비어 있으면 -> 최대값 & 최소값 출력
heap.sort()
return [heap[-1] , heap[0]]
elif len(heap) < 1 : # (2) 비어 있음 -> [0,0]
return [0,0]
else : # (3) heap 이 1개 남아 있을떄 -> 최대값 = 최소값 *[테케 8,9,10]
return [heap[0] , heap[0]]
return answer