[프로그래머스 Programmers][Python] 이중우선순위큐

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

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스

백준에 있는 문제 중에는 이거랑 비슷한 것처럼 보여도 명령어 개수랑 순서 생각해서 최적화 안 하면 시간 초과 뜨는 문제들이 있다. 그런 문제 같은 건 아니니까 그냥 조건에 맞춰 구현하면 된다.

 

이 문제도 역시 킹갓파이썬의 heapq를 써서 해결한다.

 

1. operations에서 하나씩 뽑아서 명령어를 나눈다.
   1. 최솟값은 heappop으로 뽑는다
   2. 최댓값은 q.index(max(q))로 뽑는다 ->O(N)의 위엄
   3. 삽입은 heappush로 넣으면 된다.
2. 이제 max(q), q[0](heap이므로 이게 최솟값이다)로 답을 반환한다.

 

import heapq

def solution(operations):
    answer = []
    q = []

    for c in operations:
        cc = c.split()
        if cc[0] =='I':
            heapq.heappush(q,int(cc[1]))
        elif cc[0] == "D":
            if len(q)==0:
                continue
            if cc[1] =='1':
                q.pop(q.index(max(q)))
            else:
                heapq.heappop(q)


    if len(q)==0:
        return[0,0]
    else:
        return [ max(q),q[0]]

    return answer