[Heap] 프로그래머스 이중우선순위큐

출처 : 프로그래머스 이중우선순위큐 https://programmers.co.kr/learn/courses/30/lessons/42628#

코딩테스트 연습 - 이중우선순위큐

 

문제에서 정의된 이중 우선순위 큐는 다음 연산을 할 수 있는 자료 구조를 지닌다.

명령어	수신 탐(높이)
I 숫자	큐에 주어진 숫자를 삽입한다.
D 1	큐에서 최대값을 삭제한다.
D -1	큐에서 최소값을 삭제한다.

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

 

1) 힙 구조를 사용하지 않고 푸는 방법

가장 먼저 접근한 방법은 힙이 아니라 파이썬 내장 함수 max()와 min()을 이용하여 푸는 방법이다. 힙 구조를 만드는데 heapify를 사용하면 드는 시간복잡도가 O(n)정도라고 하니, max(), min()을 이용하는 것이 heapify를 이용하는 것보다 오랜 시간이 걸릴 것 같다. 

 

 

먼저 operations 리스트 안에 있는 요소들을 operation으로 두고 for문을 돌린다. 이때 operation의 첫 글자가 I인지 D인지에 따라 큐에 원소를 추가할 것인지, 삭제할 것인지를 분별한다. 따라서 첫 글자가 I인 경우, 해당 operation의 숫자 부분만 큐에 넣어주면 된다. 반면 첫 글자가 D이면서 큐에 원소가 한 개 이상 존재할 경우, 해당 operation의 3번째 글자가 1이면 최대값을 삭제하고, 아닌 경우 최소값을 삭제하면 된다. 이렇게 하면 첫 글자가 D일 때마다 큐에서 max값 혹은 min값을 찾아야 하므로 시간 복잡도가 오래 걸린다. 

def solution(operations):
    answer = []
    for operation in operations:
        if operation[0] == 'I':
            temp = operation.split()
            answer.append(int(temp[1]))
        elif len(answer) > 0:
            if operation[2] == '1':
                answer.remove(max(answer))
            else:
                answer.remove(min(answer))
    if len(answer) == 0:
        answer = [0,0]
    else:
        max_value = max(answer)
        min_value = min(answer)
        answer = [max_value, min_value]
    return answer

위 코드에서 볼 수 있듯이, 모든 operations를 처리해 주고 나면, 큐에 원소가 남은 경우와 남지 않은 경우를 구분하여 답을 내주면 된다. 이 부분에서도 역시 max, min 함수를 사용해서 시간이 더 오래 걸렸다. 해당 문제의 점수 평가에는 효율성 부분이 없어서 100점이 나오긴 했지만, 만약 효율성 부분이 있었다면 통과하지 못했을 것이다. 

---

2) 힙 구조를 사용하여 푸는 방법

힙을 이용하면 가장 첫 번째 원소가 최대 혹은 최소값에 해당하기 때문에 min(), max()함수를 사용하지 않아도 손쉽게 그 값을 구할 수 있다. 특히 파이썬은 내장 모듈로 heapq를 지원하기 때문에 코드로도 간단하게 구현할 수 있다.

 

우선 최대힙과 최소힙 두 가지를 구성하여 최대값과 최소값 모두에 접근하기 용이하도록 한다. 만약 operation의 첫 글자가 I이면 최대힙과 최소힙 모두에서 해당 숫자를 삽입하여 준다. 그리고 counter 변수를 이용해서 힙의 길이를 나타내준다. (len()함수를 이용해도 무방하지만, 변수를 이용하면 시간 절약이 되니까) 

만약 operation의 첫 글자가 D이고 세 번째 글자가 1이면 최대힙에서 0번째 원소를 pop하면 되고, 최소힙에서 해당 원소를 제거해주면 된다. 이 때, 해당 원소를 제거해 주지 않으면 이미 큐에서 제거된 원소가 한 쪽에만 남아있을 수도 있으니 유의해야 한다. 반대로 세 번째 글자가 '-'이면 최소힙에서 0번째 원소(최소값)를 pop하면 되고, 최대힙에서 해당 원소를 제거해주면 된다.

 

이 때 유의해야 할 점은 최대힙을 설계하는 과정이다. 파이썬의 heapq 모듈은 최소힙을 기본으로 하기 때문에, 최대힙을 구성하고 싶은 경우에는 튜플을 이용하여 [-값, 값]을 넣던가 내가 한 것처럼 값 * -1하여 쉽게 최대힙 처럼 사용할 수 있다. 만약 이렇게 사용한다면, 최대힙에서 나온 값들은 전부 -1을 곱해줘야 한다는 것을 기억해야 오류가 없다. 만약 파이썬의 heapq 모듈이 익숙하지 않다면, 내가 항상 참고하는 블로그를 찾아봐도 좋을 것 같다(링크 : https://www.daleseo.com/python-heapq/)

 

그 외의 다른 과정(이미 큐를 처리한 후에 답을 선택하는 과정)은 1번에서 했던 것과 동일하다. 

import heapq
def solution(operations):
    max_heap = []
    min_heap = []
    counter = 0
    for operation in operations:
        if operation[0] == 'I':
            temp = operation.split() 
            num = int(temp[1])
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap,-1*num)
            counter += 1
        elif counter != 0:
            if operation[2] == '1':
                a = heapq.heappop(max_heap)
                min_heap.remove(-1*a)
            else:
                a = heapq.heappop(min_heap)
                max_heap.remove(-1*a)
            counter -= 1
    if counter == 0:
        return [0, 0]
    else:
        return[-1 * max_heap[0], min_heap[0]]
    return answer

해당 코드는 https://github.com/430lyj/Algorithm/blob/main/priorityqueue_double.py에서도 확인하실 수 있습니다.