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

2024년 7월 15일

문제 링크 : 프로그래머스 - 이중우선순위큐

---

문제 접근

 

최소 힙과 최대 힙을 다룰 수 있는지를 묻는 문제이다.

 

문제만 읽어보면 최소 힙과 최대 힙 성질을 모두 갖는 하나의 자료구조를 만드는 것을 요구하지만, 실제로는 최소 힙과 최대 힙 두 가지 자료구조를 모두 활용하여 하나의 자료구조처럼 사용해야하는 문제이다.

 

(힙 자료구조와 우선순위 큐란? : https://ymg5218.tistory.com/120)

 

최소 힙, 최대 힙을 모두 선언하고 값을 삽입하는 연산이 들어올 때마다 해당 값을 최소 힙, 최대 힙에 모두 삽입한다.

여기서, 라이브러리가 최소 힙만 지원해준다고 최대 힙을 따로 구현할 필요는 없다. 삽입하는 값에 -1을 곱해주어 최소 힙에 저장하면, 해당 값을 꺼낼 때마다 다시 -1을 곱해주면 되기 때문이다. (왜인지 궁금하다면 위 링크 참고 바란다!)

 

여기서 중요한 점은, 실제 이중우선순위큐의 길이를 계속 갱신해주어야 한다는 점이다.

 

만약 이중우선순위큐의 실제 저장된 값이 2개라면 최소 힙, 최대 힙 또한 2개씩 저장되어 있을 것이다.

만약 최소 힙에서 1번, 최대 힙에서 1번 값을 추출하는 연산을 진행했다면 실제 이중우선순위큐에 저장된 값은 0개이지만 최소/최대 힙 각각에는 1개씩 값이 남아있어 이중우선순위큐가 비었다고 판단할 수 없다.

그렇기에 이중우선순위큐의 길이가 0일 때마다 최소/최대 힙을 비워주는 연산이 추가로 꼭 필요하다.

---

전체 코드

 

import heapq

def solution(operations):
    answer = []

    maxHeap = []
    minHeap = []
    nowLength = 0
    for _op in operations:
        op = _op.split(' ')
        if op[0] == "I":
            heapq.heappush(minHeap, int(op[1]))
            heapq.heappush(maxHeap, int(op[1]) * -1)
            nowLength += 1
        else:
            if nowLength > 0:
                if op[1] == "-1":
                    heapq.heappop(minHeap)
                    nowLength -= 1
                else:
                    heapq.heappop(maxHeap) * -1
                    nowLength -= 1
        
        # 실제 큐 길이가 0이면 둘 다 초기화
        if nowLength <= 0:
            maxHeap.clear()
            minHeap.clear()

    if nowLength <= 0:
        return [0, 0]
    else:
        answer.append(heapq.heappop(maxHeap) * -1)
        answer.append(heapq.heappop(minHeap))
        return answer

if __name__ == "__main__":
    operations = ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
    print(solution(operations))

---

풀이 후기

 
문제를 어떻게 풀어야하지 고민하다 최소 힙과 최대 힙 하나씩 이용하여 문제를 풀면 되겠다고 판단하였다.

이 문제에서 가장 중요한 것은, 실제 이중우선순위큐의 길이가 0일 때마다 모든 힙을 비워주는 부분이라고 생각한다.