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

해당 글은 프로그래머스 힙(Heap) Level 3 '이중우선순위큐'을 다룬다.

문제

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

프로그래머스

 

설명

해당 문제는 리스트를 이용한 방법과 heapq 모듈을 사용한 방법 2가지로 풀었다.

기본 원리는 비슷하나 heapq 모듈을 사용한 방법에서 리스트 q에서 최대값을 제거한 후 heapify를 해주어 변경된 리스트 q를 다시 힙으로 변환하는 과정이 있어야 힙의 구조를 깨뜨리지 않을 수 있다.

하지만, 해당 문제에서는 heapify를 해주지 않아도 제출성공하는데 지장이 없었다.

 

코드

def solution(operations):
    answer = [0, 0]
    q = []
    for i in range(len(operations)):
        temp = operations[i].split(' ')
        if temp[0] == 'I':
            q.append(int(temp[1]))
        else:
            if len(q) != 0:
                if temp[1] == '1':
                    q.remove(max(q))
                else:
                    q.remove(min(q))
    if len(q) != 0:
        answer = [max(q), min(q)]
    return answer

 

import heapq
def solution(operations):
    answer = [0, 0]
    q = []
    
    for i in range(len(operations)):
        temp = operations[i].split(' ')
        if temp[0] == 'I':
            heapq.heappush(q, int(temp[1]))
        else:
            if len(q) != 0:
                if temp[1] == '1':
                    q.remove(max(q))
                    heapq.heapify(q)
                else:
                    heapq.heappop(q)
    if len(q) != 0:
        answer = [max(q), min(q)]
    return answer