힙을 통해 삽입되는 수를 정렬한다.
빈 큐에서 삭제 명령어는 무효
라는 조건을 고려해 힙의 원소 개수를 파악해 삭제 명령어가 유효한 경우를 판단한다.
삽입되는 수를 정렬하고 순서에 맞춰 입력되는 최댓값, 최솟값 삭제 명령어를 실행해야 한다. 힙을 통해 효율적으로 수를 정렬한다. 최댓값과 최솟값을 삭제하는 것은 정렬된 상태의 수 리스트에서 그 수만큼 잘라내는 것과 같기 때문에 삭제 명령어의 개수를 카운트했다.
하지만 빈 큐의 경우(즉 현재 삽입되어 있는 원소 수보다 지금 시점까지 나온 삭제 명령어가 더 많을 때) 삭제 명령어는 무효이기 때문에 조건문을 통해 확인해주었다.
import heapq
def solution(operations):
heap = []
max_cnt = 0
min_cnt = 0
heap_size = 0
for operation in operations:
if operation == "D 1":
max_cnt += 1
elif operation == "D -1":
min_cnt += 1
else:
oper, digit = operation.split()
digit = int(digit)
heapq.heappush(heap, digit)
heap_size += 1
# 삽입되는 순서대로 최소 힙
if max_cnt + min_cnt >= heap_size:
max_cnt = 0
min_cnt = 0
heap_size = 0
heap = []
# 빈 힙에 삭제 명령어가 들어온 경우 모든 카운트와 힙을 리셋
queue = []
while heap:
queue.append(heapq.heappop(heap))
# heappop으로 순서대로 정렬된 수를 담은 큐
if max_cnt + min_cnt >= len(queue): return [0, 0]
# 남아 있는 수가 없을 때 디폴트 값 return
queue = queue[min_cnt:len(queue)-max_cnt+1]
# 남아 있는 수가 있을 때 정렬된 목록에서 앞에서/뒤에서 삭제할 개수만큼 없애고 최댓값, 최솟값을 return
return [queue[-1], queue[0]]