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

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

코딩테스트 연습 - 이중우선순위큐

 

문제유형 : 우선순위큐, 힙

 

문제풀이 : 

• 이전에 백준에서 풀었던 문제랑 똑같아서 2개의 큐를 어떻게 동기화하는지에 대한 방법을 금방 기억할 수 있었다. (인덱스 이용!)
• 근데 테스트케이스 한개가 자꾸 틀려서 봤더니 마지막에도 한번더 확인해줘야한다는것을 생각하지 못했다.
  • 1삽입,2삽입,3삽입,4삽입, 최대삭제, 최대삭제, 최소삭제, 최소삭제, 5삽입, 6삽입의 테스트케이스가 그렇다.
  • 만약 마지막에 한번더 처리를 해주지않으면 이때 최소힙에는 [3,4,5,6]이, 최대힙에는 [1,2,5,6] 이 존재하게되므로 여기서 정답을 출력하면 답[6,5]가 아닌 [6,3]이 나오게된다..
  • 최소힙에있는 3,4는 이미 삭제된것인데 처리를 안해줬기때문

 

 

정답코드 : 

import heapq
def solution(operations):
    answer = []
    max_q = []
    min_q = []
    
    delete_idx = []
    
    for idx, op in enumerate(operations):
        order, num = op.split()
        num = int(num)
        if order == 'I':
            heapq.heappush(max_q, (-num, idx))
            heapq.heappush(min_q, (num, idx))
        else:
            if num == -1: # 최솟값 삭제
                while min_q and max_q:
                    num, idx = heapq.heappop(min_q)
                    #print(num, "최솟값삭제 ")
                    if idx in delete_idx:
                        continue
                    else:
                        delete_idx.append(idx)
                        break   
            else:
                while max_q and min_q:
                    num, idx = heapq.heappop(max_q)
                    #print(-num, "최댓값삭제 ")
                    if idx in delete_idx:
                        continue
                    else:
                        delete_idx.append(idx)
                        break   
    
    if not max_q or not min_q:
        return [0,0]
    
    while max_q:
        num, idx = heapq.heappop(max_q)
        if idx in delete_idx:
            continue
        max_val = -num
        break
    while min_q:
        num, idx = heapq.heappop(min_q)
        if idx in delete_idx:
            continue
        min_val = num
        break
        
    return [max_val, min_val]