[프로그래머스] 이중 우선 순위 큐 (python)

문제 링크

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

프로그래머스

 

 

문제

 

풀이

- 1T( 실패: IndexError: index out of range )

import heapq

def solution(operations):
    # 최대힙, 최소힙 빈 리스트
    max_pq=[]
    min_pq=[]
    for i in operations:
        # I면 숫자 삽입 
        # 최소는 그대로, 최대는 -붙여서
        # 숫자 빼고 넣을 땐, 최소 최대 둘다 적용
        if i[0]=='I':
            _,num=i.split(' ')
            num=int(num)
            heapq.heappush(min_pq,num)
            heapq.heappush(max_pq,-num)

        # 최소힙 1번 삭제, 최대힙에선 찾아서 삭제
        elif i=='D -1':
            min_val=heapq.heappop(min_pq)
            max_pq.remove(-min_val)
            heapq.heapify(max_pq)

        elif i=='D 1':
            max_val=heapq.heappop(max_pq)
            min_pq.remove(-max_val)
            heapq.heapify(min_pq)

    if not min_pq:
        return [0,0]
    else:
        max_val = -max_pq[0]
        min_val = min_pq[0]
        return [max_val, min_val]

 

heapq.heappop을 호출할 때 힙이 비어 있는 경우를 고려해야 한다.

 

따라서 

elif operation == 'D -1' and min_pq:

elif operation == 'D 1' and max_pq:

로 뒤에 리스트가 존재한다는 조건을 추가로 붙여줬다.

 

 

- 2T(성공)

import heapq

def solution(operations):
    # 최대힙, 최소힙 빈 리스트
    max_pq=[]
    min_pq=[]
    for i in operations:
        # I면 숫자 삽입 
        # 최소는 그대로, 최대는 -붙여서
        # 숫자 빼고 넣을 땐, 최소 최대 둘다 적용
        if i[0]=='I':
            _,num=i.split(' ')
            num=int(num)
            heapq.heappush(min_pq,num)
            heapq.heappush(max_pq,-num)

        # 최소힙 1번 삭제, 최대힙에선 찾아서 삭제
        elif i=='D -1'and min_pq:
            min_val=heapq.heappop(min_pq)
            max_pq.remove(-min_val)
            heapq.heapify(max_pq)

        elif i=='D 1'and max_pq:
            max_val=heapq.heappop(max_pq)
            min_pq.remove(-max_val)
            heapq.heapify(min_pq)

    if not min_pq:
        return [0,0]
    else:
        max_val = -max_pq[0]
        min_val = min_pq[0]
        return [max_val, min_val]