[Python - Lv.3] 이중우선순위큐

문제

프로그래머스

문제

문제

문제 이해

• 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조
  1. I 숫자 : 큐에 주어진 숫자 삽입
  2. D 1 : 큐에서 최댓값 삭제
  3. D -1 : 큐에서 최솟값 삭제
• 연산 operations을 처리한 뒤 큐가 비어있으면 [0, 0], 비어있지 않으면 [최댓값, 최솟값] 반환
• 빈 큐에 데이터를 삭제하라는 연산일 경우 해당 연산 무시

풀이 (1)

operations의 입력에 맞게 조건문을 작성하여 index, max, min, pop 메서드를 활용하여 해결
시간 복잡도가 O(n)인 메소드들을 마구잡이로 섞어서 시간 초과가 나올 것이라 예상

코드

문제에 정확성 테스트만 존재하고, 효율성 테스트는 존재하지 않았고 이렇게 코드를 작성해도 해결되었다.. pop, index, max, min은 모두 O(n)의 시간 복잡도를 갖고 있으며, pop/index/max를 모두 함께 사용할 경우 최대 O(n^3)의 시간 복잡도가 된다. 따라서 해당 코드는 최악이라고 할 수 있을 것이다. 이렇게 해서 끝내면 공부를 제대로 할 수 없으므로 힙으로도 풀어보기로 한다.

def solution(operations):
    result = []
    
    for op in operations:
        if op[0] == 'I':
            result.append(int(op[2:]))
        elif op == "D 1":
            if len(result) != 0:
                result.pop(result.index(max(result)))
        else:
            if len(result) != 0:
                result.pop(result.index(min(result)))

    if len(result) == 0:
        return [0, 0]
    else:
        return [max(result), min(result)]

정확성 테스트

풀이 (2)

최소 힙과 최대 힙을 모두 사용하여 최댓값과 최솟값에 동시에 접근
최댓값을 제거하면, 최소합을 동기화하는 작업 필요
최솟값을 제거하면, 최대힙을 동기화하는 작업 필요

코드

여기서 remove와 heapify는 모두 O(n)의 시간 복잡도를 갖고 있고, heappop과 heappush는 O(log n)의 시간 복잡도를 갖고 있다. 결국 이 코드의 시간 복잡도는 remove와 heappop을 함께 사용한 부분에 의해 O(n log n)이 된다. 하지만 풀이 (1)과 비교했을 때, 실행 시간이 오히려 증가한 것을 확인할 수 있다. 따라서 테스트 케이스와 효율성 테스트가 추가돼야 한다고 생각한다.

import heapq

def solution(operations):
    max_heap = []
    min_heap = []
    
    for op in operations:
        if op == "D 1":
            if max_heap != []:
                min_heap.remove(-heapq.heappop(max_heap))
                heapq.heapify(min_heap)
        
        elif op == "D -1":
            if min_heap != []:
                max_heap.remove(-heapq.heappop(min_heap))
                heapq.heapify(max_heap)
        else:
            heapq.heappush(max_heap, int(op[2:]) * -1)
            heapq.heappush(min_heap, int(op[2:]))

    if max_heap == []:
        return [0, 0]
    else:
        return [-max_heap[0], min_heap[0]]

정확성 테스트