[프로그래머스] 이중우선순위큐(파이썬,heapq)

1. 문제

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

프로그래머스

 

 

2. 풀이

우선순위 큐 heapq 이용함

(1) I인 경우 heappush

(2) D -1 인 경우 -> 빈 배열인지 확인 후 아니면 pop하면 최소값 빠짐 

(3) D 1 인 경우 -> 빈 배열인지 확인 후 아니면 max값 구해서 remove

<처음 안 사실>

- [16,16,16] 에서 remove(16)을 하면 []가 아니라 [16,16] 임

- 우선순위큐로 q를 이용하고 있지만 애초에 리스트 타입이라 max 값 구해서 뺴줘도 됨( 최대힙 따로 안구해도 된단 뜻)

 

 

 

3. 코드

import heapq
def solution(operations):
    answer = [0,0]
    q= []
    for oper in operations:
        inst, num = oper.split()
        if inst == "I":
            heapq.heappush(q,int(num))

        elif inst == "D" and num[0] == "-":
            if len(q) !=0:
                heapq.heappop(q)

        else:
            if len(q) != 0 :
                find_max = max(q)
                q.remove(find_max)
                
        print(q)
        
    if len(q) !=0:
        answer[0] = max(q)
        answer[1] = min(q)
    return answer

 

 

 

 

 

* heapq에 익숙해지기 위해 최대힙으로 위의 문제를 풀어본 코드

import heapq
def solution(operations):
    answer = [0,0]
    q= []
    for oper in operations:
        inst, num = oper.split()
        if inst == "I":
            heapq.heappush(q,-int(num))

        elif inst == "D" and num[0] == "-":
            if len(q) != 0:
                max_q = max(q)
                q.remove(max_q)

        else:
            if len(q) != 0:
                heapq.heappop(q)
                
        print(q)
        
    if len(q) !=0:
        answer[1] = -max(q)
        answer[0] = -min(q)
    return answer