[코딩테스트] 프로그래머스 - 이중우선순위큐

1. 아이디어

▪ 최대 heap, 최소 heap, 이중우선순위큐에 해당 원소가 몇개 있는지 기록할 딕셔너리 초기화 

▪ operations를 하나씩 받아서 다음을 수행

   - ' I 숫자'를 입력 받았을 경우

      - 최대 heap과 최소 heap에 push

      - 해당 숫자가 이중우선순위큐에 몇개 있는지 갱신 

   - 'D 1'를 입력 받았을 경우 

      - 최대 heap에서 최대값 pull하는 while문 반복

         - 꺼낸 최대값이 이중우선순위큐에 1개 이상 존재하면 해당 원소 개수 -1하고 break  

   - 'D -1'를 입력 받았을 경우 

      - 최소 heap에서 최소값 pull하는 while문 반복

         - 꺼낸 최소값이 이중우선순위큐에 1개 이상 존재하면 해당 원소 개수 -1하고 break  

▪ 이중우선순위큐에 있는 원소만 추출해서 최대값, 최소값 return 

2. 시간복잡도

▪ O(NlogN)

3. 변수

▪ 원소의 개수 딕셔너리: dict

▪ 최소 heap, 최대 heap: heap

Code

import heapq

def solution(operations):
    max_q = []
    min_q = [] 
    chk = {} 
    
    for x in operations:
        op,num = x.split()
        num = int(num)
        
        if op == 'I':
            heapq.heappush(min_q, num)
            heapq.heappush(max_q, num*-1)
            
            if num not in chk:
                chk[num] = 1
            else:
                chk[num] += 1
                
        elif op == 'D' and num == 1 and len(max_q) > 0:
            while max_q:
                removed_num = heapq.heappop(max_q) * -1
                
                if chk[removed_num] > 0:
                    chk[removed_num] -= 1 
                    break
            
        elif op == 'D' and num == -1 and len(min_q) > 0:
            while max_q:
                removed_num = heapq.heappop(min_q)
                
                if chk[removed_num] > 0:
                    chk[removed_num] -= 1 
                    break
    rs = []
    for i in chk:
        if chk[i] > 0:
            rs.append(i)
    
    if len(rs) == 0:
        answer = [0,0]
    else:
        answer = [max(rs),min(rs)]
    
    return answer

 

프로그래머스