방구석프로의 이야기

https://school.programmers.co.kr/learn/courses/30/lessons/42628

문제 해결을 위한 과정

이 문제는 heapq를 2개 만들어서 해결하면 쉽게 해결할 수 있는 문제였습니다.

파이썬의 경우 최소 힙 방식이므로 heapq에서 pop 하면 최솟값이 나온다는 것을 염두에 두면 다른 힙에는 원래 수에 -1을 곱한 값을 넣어서 최댓값을 꺼낼 수 있다는 것을 알 수 있습니다. 그림으로 표현하면 다음과 같습니다.

힙을 2개 만들어서 첫번째 힙에는 원래대로 숫자를 삽입, 두 번째 힙에는 -1을 곱한 수를 넣었습니다. 이렇게 하면 첫 번째 힙에서 pop 하면 최솟값을, 두 번째 힙에서는 pop한뒤 -1을 곱하면 최댓값을 pop 할 수 있게 됩니다.

소스코드

import heapq

def solution(operations):
    answer = []
    maxQ = []
    minQ = []
    for i in range(len(operations)):
        cmd, num = operations[i].split()
        num = int(num)
        if cmd == "I":
            heapq.heappush(maxQ, (num))
            heapq.heappush(minQ, (num*-1))
        elif cmd == "D":
            if num == -1 and len(maxQ) != 0:
                delNum = heapq.heappop(maxQ)
                for i in range(len(minQ)):
                    if minQ[i] == delNum*-1:
                        minQ.pop(i)
                        break
            elif num == 1 and len(maxQ) != 0:
                delNum = heapq.heappop(minQ)
                for i in range(len(maxQ)):
                    if maxQ[i] == delNum*-1:
                        maxQ.pop(i)
                        break
    if len(maxQ) == 0 and len(minQ) == 0:
        answer.append(0)
        answer.append(0)
    else:
        answer.append(heapq.heappop(minQ)*-1)
        answer.append(heapq.heappop(maxQ))
    return answer