[프로그래머스/파이썬] 이중우선순위큐 풀이 (힙, Python, heap, heapq)

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

(힙, Python, heap, heapq, heappop, heappush, remove)

[프로그래머스/파이썬] 이중우선순위큐 풀이 (힙, Python, heap, heapq)

 

1. 문제

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

---

2. 문제 해결 아이디어 (풀이)

 

1. 힙을 사용한다.

 

2. 최소힙과 최대힙 배열을 따로 만들어서 각각 삽입/삭제를 진행한다

 

2.1. 값 삭제를 할 때,

- 최댓값 삭제는 최대힙을 pop 해준 뒤, 최소힙에 해당 최댓값을 remove로 삭제한다.

- 최솟값 삭제는 최소힙을 pop 해준 뒤, 최대힙에 해당 최솟값을 remove로 삭제한다.

** 이때, remove할때 -최댓값, -최솟값 이렇게 -를 붙여줘야 한다. 

** 최대힙은 구현을 위해 임시로 -를 붙이기 때문이다. (파이썬은 기본적으로 최소힙만 있음)

 

 

3. 배열을 순회하며 옵션에 따라 적절한 계산을 진행하면 된다.

---

3. 코드

import heapq

def solution(operations):
    answer = []
    
    # 1. 힙 만들기
    minHeap = []
    maxHeap = []
    
    # 2. operations 배열을 순회하며 작업 진행
    for operation in operations:
        nowOperation = operation.split() 
        
        option = nowOperation[0]
        num = int(nowOperation[1]) # int형으로 바꾼다.
        
        # 2.1. 삽입 
        if option == 'I':
            heapq.heappush(minHeap, num) # 최소힙
            heapq.heappush(maxHeap, -num) # 최대힙 (-로 넣어야 최대)
        # 2.2. 삭제
        elif option == 'D' and minHeap: # 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시
            if num == 1: # 최댓값 삭제
                numMax = heapq.heappop(maxHeap) # (-로 나온다)
                # 최솟값도 같이 삭제해준다.
                minHeap.remove(-numMax) # (-를 +로 바꿔줌)
            elif num == -1: # 최솟값 삭제
                numMin = heapq.heappop(minHeap)
                maxHeap.remove(-numMin) # maxHeap도 삭제. (-를 +로 바꿔줌)
                
    # 3.1. 남은 값에 따라 [최댓값, 최솟값 리턴]
    if minHeap: #힙에 값이 남아있다면?
        print(minHeap)
        return [max(minHeap), min(minHeap)]
    else : # 힙에 값이 없다면?
        return [0,0]
            
    
    return answer

 

사용한 파이썬 힙 라이브러리 및 함수 설명은 아래와 같다.

 

1. heapq.heappush (힙, 값) : 힙을 추가한다

2. heapq.heappop (힙) : 힙에서 최솟값을 꺼내고 반환한다.

3. 배열.remove(값) : 배열에서 해당 값을 삭제한다. (index가 아니고 '값'으로 삭제한다.)

 

---

4. 마무리

이 문제는 2번만에 스스로 풀 수 있게 됐다..! 

요즘 문제들을 복습하고 있는데, 확실히 복습하니 문제를 푸는 속도도 점점 빨라지고 익숙해지는 것 같다!

화이팅!