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

문제

 

 

 

 

이 문제는 heap 을 사용하여  처리해주어야한다. 왜냐하면 operations 의 길이가  1,000,000 이하  이기 때문에 이를 고려해서 시간이 초과되지 않도록 해주어야 하기 때문이다.

 

 

명령어를 인식해서 처리해주는 부분은 리스트 인덱스를 통해서 처리해주었다.

 

import heapq

def solution(operations):
    answer = []
    heap = []
    for i in operations:
        #값 삽임
        if i[0] == "I":
            n = int(i[2:])
            heapq.heappush(heap,n)
        #최솟값 삭제
        if i[0] == "D" and i[2] == "-":
            if len(heap)>0: 
                heapq.heappop(heap)
        #최댓값 삭제
        if i[0] == "D" and i[2] =="1":
            if len(heap)>0:
                mx = max(heap)
                heap.remove(mx)
            
    if len(heap)>0:
        answer.append(max(heap))
        answer.append(heapq.heappop(heap))
    else:
        answer.append(0)
        answer.append(0)

    return answer

 

삽입 해준 값을 변환해주는 부분도 리스트 인덱싱을 통해 숫자 부분만 떼어준 후 int 로 형변환을 시켜주어 해결하였다.

 

최소힙과 최대힙을 구현하려다가 그렇게 되면 최댓값을 삭제할 때 최소힙의 값에서도 찾아서 삭제해주어야하는 문제가 있어서 max를 활용하여 최댓값을 구하고 최솟값는 heappop를 통해 구하는 방식으로 문제를 해결해주었다.