[프로그래머스 Lv.3] 이중 우선 순위큐

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

프로그래머스

 

✅ 1차 풀이 

import heapq


def solution(operations):
    heap = []
    for operation in operations:
        [inst, value] = operation.split(' ')
        value = int(value)
        if inst == 'I':
            # heap 삽입
            heapq.heappush(heap, value)

        elif heap:
            if value > 0:
                # maxHeap을 생성하기 위해 부호 반대로 변경
                for i in range(len(heap)):
                    heap[i] = -heap[i]
                heapq.heapify(heap)
                heapq.heappop(heap)
                # 다시 부호 돌려놓기
                for i in range(len(heap)):
                    heap[i] = -heap[i]
                heapq.heapify(heap)
            else:
                heapq.heappop(heap)


    if not heap:
        return [0, 0]

    return [max(heap), heap[0]]

일단 문제의 해결 로직은 간단한 문제였다.

삽입, 삭제 (최대값, 최소값) 명령을 수행해 힙에 넣어주고, 명령을 모두 수행하고 남은 힙에서 최소값과 최대값을 담아 리턴해주면된다.

 

일단, 최대, 최소값을 보고 힙으로 문제를 접근하였는데,

고민되는 포인트로는 기본적으로 힙은 최소힙을 가지는데, 최대힙을 구현하기위해서 부호만 반대로 넣었다가 뺄때 다시 돌려주면 된다.

하지만, 명령에 따라 최소,최대값을 번갈아가면서 추출해야하다보니, 이게 이 문제를 해결하는 포인트인것 같다.

 

일단, 떠오르는 방법은 3가지였다.

1. 최대값을 추출하기 위해 heap을 잠시 최대힙으로 변경하고, 다시 돌려놓는다.

2. 오름차순 sort를 한뒤, 첫번째 요소를 제거한다.

3. max값을 찾고, remove(max_value)으로 제거한다. 

 

각 방법의 시간복잡도를 비교해보자.

1. 부호 반전 O(n) + 최대 힙 변환 O(n) + 최대값 root 추출 O(logn) + 부호 반전  O(n) +최소 힙 변환 O(n)=O(n)

2. 오름차순 정렬 O(n log n) + 첫번째 요소 제거 O(1)+ 다시 heapify O(n)

3. max값 찾기 O(n) + remove O(n) + 다시 heapify O(n)

 

2번을 제외하고는, 시간복잡도가 동일하므로 차이가 나지않는다. 

 

 

 

✅ 다른 풀이 (3번 방식)

import heapq


def solution(operations):
    heap = []
    for operation in operations:
        [inst, value] = operation.split(' ')
        value = int(value)
        if inst == 'I':
            heapq.heappush(heap, value)

        elif heap:
            if value > 0:
                heap.remove(max(heap))
            else:
                heapq.heappop(heap)


    if not heap:
        return [0, 0]

    return [max(heap), heap[0]]

3번 방식이 더 깔끔하고, 직관적인 코드이므로, 더 좋은 방법인것 같다!