[Python] 프로그래머스(Lv3) / 백준(BOJ) - 이중 우선순위 큐

안녕하세요 :)

먼저 이문제는 프로그래머스가 테케가 부족한 문제입니다.

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

이 문제의 해답을 보면 대부분 O(n^2) 또는 (n^2logn) 입니다.
허나 이 문제에서 진짜 원하는 해답은 O(nlogn) 만에 푸는 것입니다.

heapq 로 푼다 한들 값을 찾고 remove 메소드를 쓰면 O(nlongn) 만큼 걸리고, for문이 n번 돌기 때문에 결국 O(n^2logn) 이 됩니다.

이러면 배열로 푸는 것보다 좋지 못한 성능이됩니다.

nlargest로 푼 해답도 있으나 nlargest가 O(n*log(t))라서 결국 O(n^2)이 되겠네요 .....

어떻게 풀든 프로그래머스에서 답은 통과가 됩니다 .. 허허

** 배열로 푼 코드입니다. O(n^2)

def solution(operations):
    arr = []

    for i, oper in enumerate(operations):
        if oper == "D 1":
            if arr:
                arr.remove(max(arr))
        elif oper == "D -1":
            if arr:
                arr.remove(min(arr))
        else:
            temp = oper.split("I ")
            arr.append(int(temp[1]))

    if arr:
        # print(arr)
        return [max(arr), min(arr)]
    else:
        return [0, 0]

==================================================================

백준에 똑같은 문제가 있습니다. 위의 배열코드로 풀면 시간초과가 납니다.
https://www.acmicpc.net/problem/7662

아래와 같이 visited 를 이용해 key값으로 min_heap 과 max_heap을 동기화해주면 정답이 됩니다.

문제 제한사항에서

Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)

라고 했기 때문에 visited 길이를 1,000,000로 해주었습니다.

key값으로 다른 힙에서 삭제된 아이템인지 아닌지를 판단하고, 이미 삭제된 아이템일 경우 동기화해서 삭제합니다.

order를 다 수행하고나서도 동기화하지 못한 아이템들이 있을 수 있어 마지막에도 동기화를 해주면서 삭제해줍니다.

import sys
import heapq


def item_pop(q, visited):
    while q and not visited[q[0][1]]:
        heapq.heappop(q)

case_num = int(input())

for _ in range(case_num):
    max_heap, min_heap = [], []
    visited = [False] * 1000000

    order_num = int(input())
    for key in range(order_num):
        order = sys.stdin.readline().split()
        if order[0] == "I":
            heapq.heappush(min_heap, (int(order[1]), key))
            heapq.heappush(max_heap, (-int(order[1]), key))
            visited[key] = True
        elif order[0] == "D":
            if order[1] == "1":
                item_pop(max_heap, visited)
                if max_heap:
                    visited[max_heap[0][1]] = False
                    heapq.heappop(max_heap)
            elif order[1] == "-1":
                item_pop(min_heap, visited)
                if min_heap:
                    visited[min_heap[0][1]] = False
                    heapq.heappop(min_heap)
      
    item_pop(max_heap, visited)
    item_pop(min_heap, visited)

    if max_heap:
        print(-max_heap[0][0], min_heap[0][0])
    else:
        print("EMPTY")