[백준/Python] 7662번: 이중 우선순위 큐

문제

https://www.acmicpc.net/problem/7662

(요약)

• 삽입 명령 시, 우선순위 큐에 데이터를 삽입한다.
• 삭제 명령 시, 우선순위 큐에서 최소값 혹은 최대값 데이터를 삭제한다.
• 이때 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)

풀이 과정

처음엔 우선순위 큐를 하나만 가지고 운영하면서 최대값/최소값 명령에 따라 그때그때 최소힙/최대힙으로 변환하는 작업을 고려했다. 하지만 이 경우 최소힙/최대힙으로 재정렬하는 작업이 반복되어 비효율적이고, 시간제한도 지키기 힘들다.

따라서 힙 자체를 최소힙, 최대힙 두개로 운영하여 최소값 삭제 명령시 최소힙에서 heappop()을 호출, 최대값 삭제 명령시 최대힙에서 heappop()을 호출하는 방향으로 구현하고자 했다.

이때 최소힙과 최대힙의 동기화를 고려해야 한다. (최소힙에서 이미 삭제한 데이터를 최대힙에서 최대값으로 찾는 오류 방지 차원.. 그 반대도 마찬가지)

나는 deleted 리스트를 사용해 이미 삭제된 데이터인지 표시해두고, 힙에서 이미 삭제된 데이터는 제외하고 최대값/최소값을 판별할 수 있도록 아래와 같이 코드를 구성했다.

풀이

import sys
input = lambda: sys.stdin.readline().rstrip()
import heapq

t = int(input())
for _ in range(t):
    k = int(input())
    maxH = []
    minH = []
    deleted = [False] * k
    
    for i in range(k):
        comm = list(map(str, input().split()))
        c = comm[0]
        n = int(comm[1])
        
        if c == "I":
            heapq.heappush(maxH, (-n, i))
            heapq.heappush(minH, (n, i))
            
        else:
            if n == 1: #최대값 삭제
                while maxH and deleted[maxH[0][1]]:
                    heapq.heappop(maxH)
                if maxH:
                    deleted[maxH[0][1]] = True
                    heapq.heappop(maxH)
            else: #최소값 삭제
                while minH and deleted[minH[0][1]]:
                    heapq.heappop(minH)
                if minH:
                    deleted[minH[0][1]] = True
                    heapq.heappop(minH)

    while maxH and deleted[maxH[0][1]]:
        heapq.heappop(maxH)
    while minH and deleted[minH[0][1]]:
        heapq.heappop(minH)
        
    if maxH and minH:
        print(-maxH[0][0], minH[0][0])
    else:
        print("EMPTY")

번외

내장함수 min max를 사용하면 안될까?

(1) 의사코드

k = int(input())
h = []

for i in range(k):
    comm, n = input().split()
    
    if comm == "I": # (1) 데이터 삽입 
        h.append(n)
        
    else:
        if n == 1: 
            # (2) 최대값 삭제
            maxN = max(h)
            h.remove(maxN)
        else:
            # (3) 최소값 삭제
            minN = min(h)
            h.remove(minN)

• max(), min() 연산은 리스트를 순차 탐색하면서 최대값/최소값을 찾으므로 O(n)의 시간복잡도를 갖는다.
• remove() 연산은 리스트를 순차 탐색하면서 특정값을 삭제하므로 O(n)의 시간복잡도를 갖는다.

(2) 시간 복잡도 분석

• 삽입 명령: O(1)
• 삭제 명령: O(k*k)
  • 최대/최대값 탐색에 O(k)
  • 삭제 작업에 O(k) 소요
• 최악의 경우(k=1,000,000), O(1,000,000^2) = O(10^12) 연산이 필요
• 1초에 1억회 연산이라고 어림잡을 때 10,000초가 소요되어 시간초과

(3) 결론
당연히 안된다. (^^;)