문제 조건

input

• push, pop에 대한 작업을 나타내는 배열 operations
  • 1 ≤ operations.len ≤ 1,000,000

output

• 작업을 모두 수행하고 남아 있는 [최대, 최소]

문제 해석

• heap을 통해 우선 순위 큐로 해결해야함
  • 시간 복잡도 O(nlogn)
• max, min 각각의 힙을 만든 후, 작업에 따라 동기화
  • 단, 힙이 비어있을 경우 삭제 작업은 무시됨
  • 삭제의 경우, 1이면 최대 값을 -1이면 최소 값을 삭제한다.

코드

import heapq

def solution(operations):
    min_heap = []
    max_heap = []
    heapq.heapify(min_heap)
    heapq.heapify(max_heap)
    
    for operation in operations:
        operation = operation.split()
        work = operation[0]
        num = int(operation[1])
        
        if work == 'I':
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap, -num)
        
        else:
            if max_heap and min_heap:
                if num == 1:
                    max_num = heapq.heappop(max_heap)
                    min_heap.remove(-max_num)
                else:
                    min_num = heapq.heappop(min_heap)
                    max_heap.remove(-min_num)
                
    return [0, 0] if not max_heap and not min_heap else [-(heapq.heappop(max_heap)), heapq.heappop(min_heap)]