728x90
풀이
import heapq
def solution(operations):
answer = []
minheap = []
maxheap = []
for ins in operations:
a, b = ins.split(' ')
b = int(b)
if a == 'I':
#heapq에 push
heapq.heappush(minheap, b)
heapq.heappush(maxheap, -b)
elif a == 'D':
#heapq에 delete
try:
if b < 0:
min_value = -(heapq.heappop(minheap))
maxheap.remove(min_value)
else:
max_value = -(heapq.heappop(maxheap))
minheap.remove(max_value)
#heap이 비어있는 경우 - 명령어 무시
except IndexError:
continue
else:
break
# 명령어 완료
try:
max_value = -(heapq.heappop(maxheap))
except IndexError:
max_value = 0
try:
min_value = heapq.heappop(minheap)
except IndexError:
min_value = 0
answer.append(max_value)
answer.append(min_value)
return answer
내 풀이
- minheap과 maxheap을 같이 만들어 동작. minheap에서 pop을 하면 maxheap에서는 remove로 지우고, 반대일 경우도 마찬가지로 진행하여 두 heap이 동일한 자료를 가지도록 함.
- 파이썬 heapq는 최소힙으로 구현되므로 최대힙을 만들기 위해서는 -를 붙여서 만들었음 (6, 9가 들어간 경우 -를 붙이면 heapq는 -9, -6 순으로 정렬하므로 이를 이용하여 최대힙을 구현함). 최대힙에서 값을 가져올 때는 다시 -를 붙여서 원래 값이 나오도록 함.
- heap 안에 값이 없는 경우는 IndexError가 발생하므로 try except 문으로 예외 처리함
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 조이스틱 (python) (0) | 2024.03.04 |
---|---|
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 체육복 (python) (0) | 2024.02.29 |
[프로그래머스 코딩테스트 고득점 Kit / 힙(Heap)] 더 맵게 (python) (0) | 2024.02.20 |
[프로그래머스 코딩테스트 고득점 Kit / 정렬] H-Index (python) (0) | 2024.02.20 |
[프로그래머스 코딩테스트 고득점 Kit / 정렬] 가장 큰 수 (python) (0) | 2024.02.02 |