[프로그래머스] 이중 우선 순위 큐 by 파이썬 (Python) : heap

https://school.programmers.co.kr/learn/courses/30/lessons/42628?language=python3 

프로그래머스

 

 

난이도 

LV 3

 

 

문제 설명

I 숫자 형태일때는 큐에 해당 숫자를 삽입한다.

D 1 형태일때에는 큐에서 최댓값을 삭제한다.

D -1 형태일때에는 큐에서 최솟값을 삭제한다.

만약 큐가 비어있다면 [0,0] 출력 아니라면 [최대값, 최소값] return 해준다.

 

 

접근법

1. 시간을 최대한 줄이기 위해 항상 맨 앞이 최소가 되는 heapq를 사용한다.
2. 파이썬은 문자열에 문자를 인덱스로 직접 접근이 가능하기에 s[0]에 대해 I 인지 D인지 확인후 처리를 해준다.
3. 만약 I라면 슬라이싱을 이용하여 숫자부분을 int로 변환해 큐에 삽입해준다.
4. 만약 D이고 큐가 비어있지 않다면 1이면 최대값 삭제, 2이면 최솟값을 삭제한다.
5. 이때 heapq를 이용했기에 맨앞의 숫자가 가장 작아 heappop으로 손쉽게 제거 가능하다.
6. 큐가 비어있지 않다면 [최대값, 최소값] return, 비어있다면 [0,0]을 return해준다.

 

 

 

코드

import heapq
def solution(operations):
    answer = []
    q = []
    for  s in operations:
        if s[0] == "I" :
            heapq.heappush(q, int(s[2:]))
        elif s[0] == "D":
            if q:
                if s[2:] == "1":
                    q.remove(max(q))
                else:
                    heapq.heappop(q)
    
    if q:
        return [max(q), min(q)]
    else:
        return [0,0]

 

---