211213 - 이중우선순위큐

◾ 이중우선순위큐 : 프로그래머스 LEVEL 3

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

문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

---

입력

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

출력

• 큐가 비었으면 [0, 0]
• 큐가 비어있지 않으면 [최대값, 최소값]

입출력 예

operations	return
["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

---

◾ 풀이

1. 해설

• 우선순위큐, 힙 등의 자료형을 2번 사용하여 해결할 수 있다.
  • 최대 우선(Max 힙)
  • 최소 우선(Min 힙)
• 우선순위큐, 힙 모두 오름차순이 기본적인 형태이므로 최대 우선 형태를 만들기 위해 해당 값에 -1을 곱하여 준다.

---

2. 프로그램

1. 우선순위큐 또는 힙을 생성한다.
2. 명령이 I, D 중 무엇인지 확인한다.
3. I일 경우
   • max, min 우선순위큐(힙)에 num을 추가한다.
   • 해당 숫자의 개수를 num_dict에 표현한다.
4. D일 경우
   • num == 1 : max 우선순위큐(힙)의 숫자를 하나 제거한다.
   • num == -1 : min 우선순위큐(힙)의 숫자를 하나 제거한다.
   • 해당 숫자의 개수를 줄인다.
   • 만약 해당 숫자의 개수가 0이면 다음 값을 제거한다.
5. 빈 우선순위큐(힙)이 있다면 [0, 0]을 반환한다.
6. 빈 우선순위큐(힙)이 없다면 최대, 최소 우선순위큐(힙)에서 [최대값, 최소값]을 반환한다.

# 우선순위큐
# 코드
from queue import PriorityQueue
def solution(operations):
    answer = []
    num_dict = {}
    max_queue = PriorityQueue()
    min_queue = PriorityQueue()

    for op in operations:
        c, num = op.split(' ')
        num = int(num)

        if c == 'I':
            num_dict[num] = num_dict.get(num, 0) + 1
            max_queue.put(-num)
            min_queue.put(num)
        else:
            if num == 1:
                if not max_queue.empty():
                    q_num = -max_queue.get()
                    while num_dict[q_num] == 0 and not max_queue.empty():
                        q_num = max_queue.get()
                    num_dict[q_num] -= 1
            else:
                if not min_queue.empty() and not min_queue.empty():
                    q_num = min_queue.get()
                    while num_dict[q_num] == 0:
                        q_num = min_queue.get()
                    num_dict[q_num] -= 1
            if num_dict[q_num] < 0 :
                num_dict[q_num] = 0

    if max_queue.empty() or min_queue.empty():
        answer = [0, 0]
    else:
        max_num = -max_queue.get()
        min_num = min_queue.get()

        while num_dict[max_num] == 0:
            max_num = -max_queue.get()
        while num_dict[min_num] == 0:
            min_num = min_queue.get()

        answer = [max_num, min_num]

    return answer

# 힙

# 코드
import heapq 
def solution2(operations):
    answer = []
    num_dict = {}
    max_heap = []
    min_heap = []

    for op in operations:
        c, num = op.split(' ')
        num = int(num)

        if c == 'I':
            num_dict[num] = num_dict.get(num, 0) + 1
            heapq.heappush(max_heap, -num)
            heapq.heappush(min_heap, num)
        else:
            if num == 1:
                if max_heap:
                    q_num = -heapq.heappop(max_heap)
                    while num_dict[q_num] == 0 and max_heap:
                        q_num = -heapq.heappop(max_heap)
                    
                    num_dict[q_num] -= 1
            else:
                if min_heap:
                    q_num = heapq.heappop(min_heap)
                    while num_dict[q_num] == 0 and min_heap:
                        q_num = heapq.heappop(min_heap)

                    num_dict[q_num] -= 1
            if num_dict[q_num] < 0 :
                num_dict[q_num] = 0

    if not max_heap or  not min_heap:
        answer = [0, 0]
    else:
        max_num = -heapq.heappop(max_heap)
        min_num = heapq.heappop(min_heap)

        while num_dict[max_num] == 0:
            max_num = -heapq.heappop(max_heap)
        while num_dict[min_num] == 0:
            min_num = heapq.heappop(min_heap)

        answer = [max_num, min_num]

    return answer