[CLASS 3]백준 7662번 - 이중 우선순위 큐

7662번 : 이중 우선순위 큐

 

힙은 힙이지만, 최대와 최소를 모두 구할 수 있는 힙을 구현해야 한다.

 

힙큐 모듈과 각각의 요소에 True 혹은 False를 같이 넣음으로써 판단해보려고 했지만.. 시간 초과에 걸려버렸다.

 

내 코드(시간 초과):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline
import heapq

for _ in range(int(input())):
    maxHeap = []
    minHeap = []
    size = 0

    for _ in range(int(input())):
        cmd = input().split()

        if cmd[0] == 'I':
            # 두 큐에 모두 삽입
            heapq.heappush(maxHeap,[-int(cmd[1]),True])
            heapq.heappush(minHeap,[int(cmd[1]),True])
            size += 1
        # 최소값을 뺄때는
        elif cmd == ['D','-1'] and size:
            # 최소 힙에서는 그냥 pop
            temp = heapq.heappop(minHeap)
            # 최대 힙에서는 뒤에서부터 검사하다 같은 수가 나오면 False로 전환
            for i in range(-1,-len(maxHeap)-1,-1):
                if -maxHeap[i][0] == temp[0] and maxHeap[i][1]:
                    maxHeap[i][1] = False
                    break
            size -= 1
        # 최대값을 뺄때는
        elif cmd == ['D','1'] and size:
            # 최대 힙에서는 그냥 pop
            temp = heapq.heappop(maxHeap)
            # 최소 힙에서는 뒤에서부터 검사하다 같은 수가 나오면 False로 전환
            for i in range(-1,-len(minHeap)-1,-1):
                if minHeap[i][0] == -temp[0] and minHeap[i][1]:
                    minHeap[i][1] = False
                    break
            size -= 1

    # 큐가 비지 않았을 경우
    if size:
        heap = [i[0] for i in minHeap if i[1]]
        print(max(heap),min(heap),sep=' ')
    else:
        print('EMPTY')

 

이렇게 작성할 경우 시간 복잡도가 O(n)이다. 그러나 통과하지 못한다. 그래서 O(logn)으로 시간 복잡도를 줄여야 겠다고 생각했다. 그러나 별 아이디어가 떠오르지 않았고, 결국 검색을 통해 정답 코드를 확인하여 작성하게 되었다.

 

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline
import heapq

for _ in range(int(input())):
    maxHeap = []
    minHeap = []
    memo = [False] * 1000000
    for k in range(int(input())):
        cmd = input().split()

        if cmd[0] == 'I':
            # 두 큐에 모두 삽입
            heapq.heappush(maxHeap,(-int(cmd[1]),k))
            heapq.heappush(minHeap,(int(cmd[1]),k))
            memo[k] = True
        # 최소값을 뺄때는
        elif cmd[1] == '-1':
            # 해당 값이 최대 힙에서 뺐던 값이라면 최소 힙에서도 제거
            while minHeap and not memo[minHeap[0][1]]:
                heapq.heappop(minHeap)
            if minHeap:
                memo[minHeap[0][1]] = False
                heapq.heappop(minHeap)
            
        # 최대값을 뺄때는
        elif cmd[1] == '1':
            # 해당 값이 최소 힙에서 뺐던 값이라면 최소 힙에서도 제거
            while maxHeap and not memo[maxHeap[0][1]]:
                heapq.heappop(maxHeap)
            if maxHeap:
                memo[maxHeap[0][1]] = False
                heapq.heappop(maxHeap)

        # 마지막에 다른 힙에서 뺐던 값을 각자의 힙에서 반영
        while minHeap and not memo[minHeap[0][1]]:
                heapq.heappop(minHeap)
        while maxHeap and not memo[maxHeap[0][1]]:
                heapq.heappop(maxHeap)

    print(f'{-maxHeap[0][0]} {minHeap[0][0]}' if maxHeap and minHeap else 'EMPTY')

 

바로 연산마다 키 값을 부여하고 value를 k값과 함께 저장하는 방법이다. 그리고 삽입이 이루어질 때마다 다른 힙에서 해당 수가 빠진 수인지 아닌지를 검사하는 방법이다. 이렇게 작성하여 제출하니 9012ms의 시간으로 통과했다.

 

제대로된 이중 우선순위 큐를 구현했다고 할 수는 없지만, 덱(deque)과 이진 검색을 이용해서 같은 결과를 내고 약간 향상된 속도로 작동하는 코드를 만들 수 있다.

 

내 코드(덱,이진 검색):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline
import bisect
from collections import deque

for _ in range(int(input())):
    l = deque()
    counts = dict()

    for _ in range(int(input())):
        cmd,i = input().split()
        i = int(i)

        if cmd == 'I':
            if i not in counts:
                # 이진 탐색으로 대입
                bisect.insort_left(l,i)
                counts[i] = 1
            else:
                counts[i] += 1
        else:
            # 비었다면 다음 연산 진행
            if not l:
                continue
            elif i == 1:
                # 1번만 들어온 값이라면
                if counts[l[-1]] == 1:
                    counts.pop(l[-1])
                    l.pop()
                else:
                    counts[l[-1]] -= 1
            elif i == -1:
                # 1번만 들어온 값이라면
                if counts[l[0]] == 1:
                    counts.pop(l[0])
                    l.popleft()
                else:
                    counts[l[0]] -= 1

    # 출력
    print(f'{l[-1]} {l[0]}' if l else 'EMPTY')

 

이렇게 작성하니 4160ms 까지 줄었다.