[프로그래머스 42628 이중우선순위큐 (level 3, 힙)

알고리즘 유형 : 힙
풀이 참고 없이 스스로 풀었나요? : X

https://programmers.co.kr/learn/courses/30/lessons/42628?language=python3

SOLVE 추가 (20230217)

힙 두 개 풀이

import sys, heapq
from collections import defaultdict
input = sys.stdin.readline

def solution(operations):
    answer = []
    
    max_hq = []
    min_hq = []
    cnt_dict = defaultdict(int)
    
    for op in operations:
        cmd, n = op.split()
        n = int(n)
        
        if cmd == "I":
            heapq.heappush(max_hq, -n)
            heapq.heappush(min_hq, n)
            cnt_dict[n] += 1
        elif cmd == "D":
            if not max_hq or not min_hq or sum(cnt_dict.values()) == 0:
                continue
            
            if n == 1:
                e = -heapq.heappop(max_hq)
                while cnt_dict[e] == 0 and max_hq:
                    e = -heapq.heappop(max_hq)
                cnt_dict[e] -= 1
            elif n == -1:
                e = heapq.heappop(min_hq)
                while cnt_dict[e] == 0 and min_hq:
                    e = heapq.heappop(min_hq)
                cnt_dict[e] -= 1
        
    if not max_hq or not min_hq or sum(cnt_dict.values()) == 0:
        return [0, 0]

    e_max = -heapq.heappop(max_hq)
    e_min = heapq.heappop(min_hq)

    while cnt_dict[e_max] == 0 and max_hq:
        e_max = -heapq.heappop(max_hq)

    while cnt_dict[e_min] == 0 and min_hq:
        e_min = heapq.heappop(min_hq)

    return [e_max, e_min]

SOLVE 1

최대 힙, 최소 힙 총 두 개의 힙을 할당하는 풀이

import heapq

def solution(operations):
    answer = []
    minHeap = []
    maxHeap = []
    
    for oper in operations:
        cmd, num = oper.split(" ")
        num = int(num)
        
        if cmd == "I":
            # 입력으로 들어온 수를 최대 힙, 최소 힙 둘 다 넣어줌. 최대 힙은 음수 테크닉!
            heapq.heappush(minHeap, num)
            heapq.heappush(maxHeap, -num)
        elif cmd == "D": # 없는데 뽑으라고 하는 경우가 있을 수 있으므로 들어있는지 체크
            if num == 1 and maxHeap:
                heapq.heappop(maxHeap)
                # 뽑으려고 하는데 힙이 비어있거나, 최대 힙의 최대값이 최소 힙의 최대값보다 작은 경우
                # 실제로는 문제 상 이중 우선순위 큐의 모든 원소가 삭제가 된 경우이므로, 두 힙을 싹 비워서 동기화해준다.
                # 후자의 경우가 무슨 말인지 이해가 잘 안될 수 있다.
                # 이미지 트레이닝을 해보자.
                # 칠판에 왼쪽에는 최소 힙, 오른쪽에는 최대 힙을 둘 다 오름차순, 세로 방향으로 수를 나열해보자. (아래가 젤 작은 수)
                # 쭉 뽑다가, 어떤 상황에서 최대 힙의 최대값이 최소 힙의 최소값보다 작은 경우가 되었다고 생각해보자.
                # 이 때 최소 힙의 최소값 아래 방향의 수들은 모두 삭제된 상태고, 최대 힙의 최대값 위에 위치했던 수들은 모두 삭제된 상태다.
                # 그런데 크기 상 최소 힙 최소값이 최대 힙 최대값보다 위에 있으므로, 위치 상으로 생각해보면
                # 두 힙에 동시에 존재하는 수가 하나도 없게 된다. 즉 이 경우는 이중우선순위큐의 모든 원소가 삭제된 경우를
                # 의미하는 것이다. 그러므로 두 힙을 빈 리스트로 동기화해준다.
                if len(maxHeap) == 0 or -maxHeap[0] < minHeap[0]:
                    minHeap = []
                    maxHeap = []
            elif num == -1 and minHeap:
                heapq.heappop(minHeap)
                if len(minHeap) == 0 or -maxHeap[0] < minHeap[0]:
                    minHeap = []
                    maxHeap = []
    
    if len(minHeap) == 0:
        answer = [0, 0]
    else:
        answer = [-heapq.heappop(maxHeap), heapq.heappop(minHeap)]
    
    return answer

SOLVE 2

heapq.nlargest(n, heap)을 활용한 풀이

import heapq

def solution(operations):
    answer = []
    heap = []
    
    for oper in operations:
        cmd, num = oper.split(" ")
        num = int(num)
        
        if cmd == "I":
            heapq.heappush(heap, num)
        elif cmd == "D" and heap:
            if num == 1:
                heap.pop(heap.index(heapq.nlargest(1, heap)[0]))
            elif num == -1:
                heapq.heappop(heap)
    
    if heap:
        answer = [heapq.nlargest(1, heap)[0], heapq.heappop(heap)]
    else:
        answer = [0, 0]
                
    
    return answer

SOLVE 3

최대값을 뽑아야할 때 최대 힙으로 바꾸고, 최소값을 뽑아야할 때 최소 힙으로 바꿔서 뽑는 풀이

import heapq

def solution(operations):
    answer = []
    heap = []
    
    for oper in operations:
        cmd, num = oper.split(" ")
        num = int(num)
        
        if cmd == "I":
            heapq.heappush(heap, num)
        elif cmd == "D" and heap:
            if num == 1:
                heapq._heapify_max(heap)
                heapq._heappop_max(heap)
            elif num == -1:
                heapq.heapify(heap)
                heapq.heappop(heap)
    
    if heap:
        answer = [max(heap), heapq.heappop(heap)]
    else:
        answer = [0, 0]
                
    
    return answer

SOLVE 추가) 풀이 요약

• 해당 문제는 시간제한과 테스트케이스가 좀 빈약한 것 같다. SOLVE 1의 경우 힙에 3을 4개 넣고 최대 두번, 최소 두번을 뽑는 경우에 오답을 내는데 제출하면 통과가 되버린다. 이 추가 풀이로는 통과하는데 대신 sum 연산에서 시간복잡도를 많이 잡아먹는다. 시간제한이 빡빡했다면 이 풀이도 오답이었을 것이다.

SOLVE 1) 풀이 요약 (최대 힙, 최소 힙 총 두 개의 힙을 할당하는 풀이)

1. 이 풀이의 핵심은 최대 힙 최소 힙을 각각 할당하는 것, 그리고 명령어 D가 들어와서 힙에서 pop을 할 때, 여러가지 예외 상황을 생각해내고 조건문으로 잘 커버하는 것이다.

2. 전체적으로 구현의 틀은 간단하다.

   명령어 operations를 for로 순회한다.

   명령어의 종류에 따라 조건문으로 나누고, 수를 넣을 때는 최소 힙, 최대 힙에 둘 다 넣어준다. (이 때 최대 힙을 구현하기 위해, 최대 힙에는 원래 수에 음수가 붙은 형태로 들어가 있게 됨을 유의)

   수를 제거해야할때는, 1일 땐 최대힙에서, -1일 땐 최소힙에서 뽑는다. 물론 힙이 비어있는지 아닌지 체크해줘야한다. (그리고 예외 상황을 처리해줘야하는데, 이 부분은 뒤에서 설명하겠다.)

   모든 명령을 처리하고 난 후, 두 힙 중 하나라도 비어있다면 이중우선순위큐가 비어있다는 의미이므로 [0, 0]을 리턴하고, 존재한다면 최대 힙의 최대값과 최소 힙의 최소값을 리스트 형태로 리턴해주면 된다.

3. 다만 명령어가 D일 때, 즉 힙에서 pop을 "하고나서" 유의해야 할 점이 두 가지가 있다.

   1) 뽑고난 뒤 힙이 비어있는 경우

   우리는 명령어 I가 들어왔을 때, 숫자를 최소 힙, 최대 힙에 각각 둘 다 넣어준다.

   어느 순간 D 1이 들어와 최대 힙에서 최대값 하나를 제거했다고 생각해보자.

   이는 문제 상 이중우선순위큐 개념에서 그 값이 제거된 것이다. 즉, 어떤 값에 대해 최소 힙과 최대 힙 중 어느 한 곳에서라도 제거되면 그 값은 이중우선순위큐에서 값이 제거된 것과 같은 의미를 가진다.

   그런데 어느 한 쪽의 힙이 완전히 비어있다면, 이중우선순위큐가 완전히 비어있다는 것을 의미함을 알 수 있다.

   즉, 뽑고난 뒤 힙이 비어있는 경우에는 두 힙을 똑같이 빈 리스트로 동기화해준다.

   
   

4. 최대 힙의 최대값이 최소 힙의 최소값보다 작은 경우

   머릿 속에 칠판을 떠올리고, 왼쪽에는 최소 힙의 원소들을 밑에서부터 오름차순으로 세로 방향으로 나열하고, 오른쪽에는 최대 힙의 원소들을 똑같은 방식으로 나열하자.

   여러 가지 명령어들을 거쳐, 두 힙은 여러 원소들이 제거되었다.

   그리고 어떠한 시점에서, 최대 힙의 최대값이 최소 힙의 최소값보다 작아졌다고 생각해보자.

   그럼 위치 상, 최소 힙의 최소값 아래로는 값이 싹 제거되었고, 최대 힙의 최대값 위의 수들도 모두 제거된 상태이다.

   그런데 최대 힙 최대값이 최소 힙 최소값보다 작으므로, 위치 상 최대 힙 최대값이 더 아래에 있다.

   여기까지 잘 떠올렸다면, 모든 수들 각각이 최소 힙 최대 힙에 동시에 존재하지 않고 한 쪽에만 존재한다는 것을 알 수 있을 것이다.

   즉, 이 경우에도 이중우선순위큐는 완전히 비어있는 것이 된다.

   그래서 이 경우에도 두 힙에 빈 리스트를 할당해준다.

SOLVE 2 풀이 요약 (heapq.nlargest(n, heap)을 활용한 풀이)

1. heapq 모듈에는 nlargest(n, heap)이라는 함가 있다. heap에서 가장 큰 수부터 n개를 찾아 리스트 형태로 리턴해주는 함수이다.

2. D 1이 들어온 경우에, 이 함수를 활용하여 heap에서 최대 값이 위치한 인덱스를 찾고, 그 인덱스의 원소를 pop하면 된다.(힙의 내용이 리스트 자료구조에 담겨있기 때문에 가능)

3. 그 외 나머지 부분은 최소 힙을 활용하여 쉽게 구현할 수 있는 부분들이다.

SOLVE 3 풀이 요약 (최대값을 뽑아야할 때 최대 힙으로 바꾸고, 최소값을 뽑아야할 때 최소 힙으로 바꿔서 뽑는 풀이)

1. 명령어 D에 대해 1이 들어오냐, -1이 들어오냐에 따라 그때 그때 힙을 최소 or 최대 힙으로 변환하여 pop을 수행한다.

2. heapq 모듈의 _heapify_max 함수와 _heappop_max 함수를 활용한다.

   heap을 최대 힙으로 변환하고, 최대 값을 pop하는 함수이다.

배운 점, 어려웠던 점

• 힙을 두 개 사용하여 하나의 값을 두 힙에 모두 넣고, 최대값은 최대 힙에서, 최소값은 최소 힙에서 빼는 것까지는 생각했는데, 어느 한 쪽의 힙이 비었을 때 두 힙을 모두 비우는 것과 최대 힙의 최대 값이 최소 힙의 최소 값보다 작아지는 경우, 그리고 이 것이 의미하는 바를 생각해내지 못했다.

  후자의 내용 같은 경우는, 최대 힙 최소 힙 리스트를 set 변환 후 차집합하여 리스트 형변환 후 정렬하고 첫 원소, 마지막 원소를 리턴하는 식으로 구현했는데, 정렬을 해야하니까 엄청 비효율적인 방식이라고 생각됐다.

• heapq의 nlargest, _heapify_max, _heappop_max 함수를 배웠고 이를 통한 색다르고 간단한 풀이도 알아볼 수 있어 유익했다.