[우선순위 큐/힙] BOJ 7662 이중 우선순위 큐

문제

7662번: 이중 우선순위 큐

 

풀이

우선 최소 힙과 최대 힙을 각각 만든다.

기본적인 아이디어는 두 힙을 서로 동기화 시키는데에 있다.

하지만 무조건 동기화만 시킨다면 시간 초과로 문제를 풀 수 없다.

 

지금부터는 자명한 정답들에 대한 내 생각이다.

 

시간 초과를 극복하기 위해서는 문제에서 요구하는 조건만 충족시키는 한에서 두 힙을 동기화 시키는 것이 가장 적절해 보인다. 즉, 두 힙을 무조건 동기화 시킬 필요가 없다는 것이다.

 

아래 사진은 예제 입력1에 두번째 케이스에서 정답을 출력하기 직전의 두 힙의 원소들이다.

두 힙을 동기화 시키는 작업을 모두 마쳤다는 의미다.

상식적으로 생각한다면 두 힙을 완전히 동일하게 관리해야 할 것이다.

하지만 문제 통과 코드를 살펴보면 실제는 그렇지 않다.

 

문제의 출력 조건을 생각해보자.

최소 힙에서 최소 값이 최대 힙에 존재하고

최대 힙에서 최대 값이 최소 힙에 존재한다면

굳이 두 힙을 무조건 동기화 시킬 필요가 없다는 것을 의미한다.

 

이를 코드에서 설명하도록 하겠다.

 

코드

import sys
import heapq

T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())

    max_heap = []
    min_heap = []
    check_list = [False] * N
    pos = 0

    for _ in range(N):
        cmd, num = sys.stdin.readline().split()
        num = int(num)

        if cmd == 'I':
                heapq.heappush(max_heap,(-num, pos))
                heapq.heappush(min_heap,(num, pos))
                check_list[pos] = True
                pos += 1
        else:
            if num > 0:               
                while max_heap and check_list[max_heap[0][1]] == False:
                    heapq.heappop(max_heap)

                if max_heap:
                    _, tmp = heapq.heappop(max_heap)
                    check_list[tmp] = False


            elif num < 0:
                while min_heap and check_list[min_heap[0][1]] == False:
                    heapq.heappop(min_heap)

                if min_heap:
                    _, tmp = heapq.heappop(min_heap)
                    check_list[tmp] = False

    while max_heap and check_list[max_heap[0][1]] == False:
            heapq.heappop(max_heap)
    while min_heap and check_list[min_heap[0][1]] == False:
            heapq.heappop(min_heap)

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

최소 힙 그리고 최대 힙에 입력할 때 입력한 순서를 같이 입력하고 check_list에 입력됐음(True)을 남긴다.

그 후 최소 힙 또는 최대 힙에서 제거 할 때 제거된 원소의 순서가 지워졌음(False)을 check_list에 남긴다.

 

while문은 최소 힙 또는 최대 힙에서 지워진 원소를 동기화 시키는 구문이다.

하지만 모든 원소를 돌며 동기화 시키는 것이 아닌

최소 힙에서는 최소값만

최대 힙에서는 최대값만 확인한다.

 

그 이유는 위에서 설명한 것과 같이 문제의 조건은 이중 우선 순위 큐에서 최소값과 최대값만 출력하면 되기때문이다.

 

즉 최소 힙의 최소값을 지운 적 없고, 최대 힙의 최대값을 지운 적 없다면 나머지 원소들이 다른 힙에서 지워졌던 아니던 상관할바가 아닌 것이다.

 

문제의 해석은 굉장히 주관적입니다. 만약 풀이의 원래 의도가 아니라고 생각된다면 댓글로 알려주시길 바랍니다.