이중 우선순위 큐

날짜 : 2023. 10. 10

사용 언어 : python

 

문제

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

 

 

코드

import heapq
INF = int(1e9)
def solution(operations):
    maxheap = list()
    minheap = list()
    hash = dict()
    cnt = 0  # 전체 큐에 남아있는 원소의 개수
    for temp in operations:
        op, num = temp.split()
        num = int(num)
        if op == "I":  # 삽입
            cnt += 1
            heapq.heappush(minheap, num)       
            heapq.heappush(maxheap, num * (-1))
            if num not in hash: hash[num] = 1
            else: hash[num] += 1
            continue
        if cnt == 0: continue  # 더이상 뺄 수 없는 상태 => 추출 연산 패스
        cnt -= 1
        if num == -1:  # 최소값 추출
            while True:
                n = heapq.heappop(minheap)
                if hash[n] > 0:
                    hash[n] -= 1  # 뺄 수 있는 값인지 체크
                    break
        else:  # 최대값 추출
            while True:
                n = heapq.heappop(maxheap) * (-1)
                if hash[n] > 0:
                    hash[n] -= 1
                    break
    if cnt == 0: return [0, 0]  # 뺄 원소가 없는 경우
    min_res, max_res = INF, INF * (-1)
    for i in list(hash.keys()):
        if hash[i] > 0:  # 최대 / 최소값 갱신
            min_res = min(min_res, i)
            max_res = max(max_res, i)
    return [max_res, min_res]

 

 

풀이

- 전체 원소의 개수 체크를 위한 해시를 만든 다음, 두 개의 리스트(minheap, maxheap)를 생성한다.

- 그 다음 일반 큐에 남아있는 원소의 개수를 뜻하는 변수 cnt를 생성한다. (I인 경우에는 증가, D인 경우에는 감소)

- 연산이 ' I '인 경우는 양쪽 큐에 삽입처리한 다음 hash에도 해당 원소의 개수를 체크한 다음 continue

- 이외의 연산은 'D' 이고, cnt가 0인 경우에는 추출할 원소가 없기 때문에 생략한다.

- 만약 남아있는 경우 cnt의 값을 1 감소시킨 다음 숫자가 -1인 경우에 minheap에서, 1인 경우에는 maxheap에서 값을 추출한다.

- 다만 maxheap은 부호가 뒤바뀌었기 때문에 heappop으로 추출 후 (-1)을 곱해준다.

- 추출 이후에는 해시를 통해 추출 가능한 수인지 체크하고, 추출 불가능하다면 해당 큐에 대하여 반복하여 비복원 추출한다.

-  만약 추출 가능한 수를 추출한 경우, 해시값을 1 감소시킨다.

- 전체 연산을 진행한 다음에는 cnt 값이 0인 경우 [0, 0]을 리턴하되, 아니라면 hash값이 1 이상인 수들 중에서 최대값과 최소값을 걸러낸다.

 

 

알게된 점

- 두 개의 우선순위 큐를 사용해서 문제를 풀어내고, hash를 통해 뽑아낼 수 있는지 여부를 체크하는 문제였다.

- 굉장히 오랫동안 남겨놓았던 문제였는데 이번에 풀어서 꽤 후련하다.

 

 

참고 사이트

-