[백준] 7662번 이중 우선순위 큐 - (Python)

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

7662번: 이중 우선순위 큐

시간 초과를 어떻게 해결하느냐가 중요했던 문제입니다. 3번의 시간초과 끝에, 문제를 풀 수 있었습니다. 

해당문제에서 중요한 것은 heap을 통한 Queue 구현인데, 바로 2개의 heap을 통해서 문제를 해결했어야 합니다. 개인적으로 시간초과를 해결하는 데까지 굉장히 어려웠던 문제였습니다.

※ 고려사항

1. heap, 방문 처리

2. 연산처리

3. 출력처리

---

1. heap, 방문 처리

해당문제에서 가장 중요한 부분이라고 생각됩니다. 시작이 잘못되면 결과도 잘못되기 마련입니다. 본인은 최소힙 1개만을 가지고 문제를 해결하려 했고, 결국 시간초과의 늪에서 벗어나지 못했습니다.. 따라서 최대, 최소 heap을 각각 생성해 주고, 이를 다루기 위해 방문처리 배열이 필요로 됩니다.

예를 들어, 삭제 연산시, 최소힙에서 값이 삭제되었으나, 최대힙에는 그 값이 남아있기 때문에 삭제가 되었는지를 판단하기 위해 방문 배열이 필요됩니다. 해당 연산을 다루는 내용은 아래에서 다루겠습니다. 코드는 다음과 같습니다.

import sys
import heapq

input = sys.stdin.readline

max_heap = []       # 최대힙
min_heap = []       # 최소힙

visit = [False] * 1_000_001     # 방문 처리, False = 삭제, True = 미삭제

 

2. 연산처리

어쩌면 문제를 풀기위해 핵심적인 알고리즘이라 생각됩니다. 앞서 언급했듯이, 이 문제는 삭제연산이 가장 중요합니다. 입력의 경우 최대, 최소힙에 원소를 삽입하면 됩니다. 단, 연산의 index를 카운팅 해 줍니다. 왜냐하면, 최소힙에서는 삭제되었으나, 최대힙에는 해당 원소가 남아있을 수 있기 때문에 해당 원소가 삭제되었는지를 판단해 주기 위해 index를 추가로 heap에 저장합니다. 최대, 최소힙을 구현하는 방법은 다른 문제에 있기 때문에 여기서는 다루지 않겠습니다.

삭제의 경우 해당 원소가 최소 또는 최대힙에서 삭제되었는지 유무를 먼저 판단합니다. 만약 최대힙에서는 삭제되었는데, 최소힙에서는 삭제되지 않았다면, 삭제된 원소를 계속해서 지워줍니다.

이 과정이 모두 끝난뒤에 최대, 최소 힙의 가장 앞 원소에 접근하여 값을 삭제시킵니다. heap의 특성상 가장 크거나 작은 값은 반드시 제일 앞에 위치하게 됩니다. 이를 코드로 구현하면 다음과 같습니다.

n = int(input())

for _ in range(n):

    t = int(input())
    for i in range(t):

        # 연산과 원소 받음
        op, num = map(str, input().split())
        num = int(num)

        # input 일때
        if op == 'I':

            # 최대힙, 최소힙에 index번호와 함께 삽입
            heapq.heappush(min_heap, (num, i))
            heapq.heappush(max_heap, ((-1)*num, i))

            # 원소있음, 미삭제 처리
            visit[i] = True
        
        # delete 일때
        elif op == 'D':
            
            # 최소값 삭제
            if num == -1:
                
                # 상대힙에 의해 삭제되었을 경우, 해당원소 계속해서 삭제
                while min_heap and not visit[min_heap[0][1]]:
                    heapq.heappop(min_heap)
                
                # 배열안에 원소 존재시, 삭제처리하고 pop
                if min_heap:
                    visit[min_heap[0][1]] = False
                    heapq.heappop(min_heap)
            
            elif num == 1:
                while max_heap and not visit[max_heap[0][1]]:
                    heapq.heappop(max_heap)
                if max_heap:
                    visit[max_heap[0][1]] = False
                    heapq.heappop(max_heap)

 

3. 출력처리

해당문제를 여기까지 접근했어도, 마지막 출력을 잘못 처리할 경우 틀리게 됩니다. 바로 최대힙과 최소힙에 삭제처리가 되지 않은 원소가 남아있을 수 있기 때문입니다. 왜냐하면 마지막 연산이 최대 또는 최소힙 1 부분에서만 삭제처리를 하기 때문에 반대 힙은 아직 원소가 남아있을 수 있습니다. 따라서 2개의 heap을 동일한 상태로 만들기 위해 삭제처리를 거친 후에, heap에 원소가 존재하면 최대, 최솟값을 출력하고 그렇지 않다면, empty를 출력합니다. 코드는 다음과 같습니다.

 # 삭제처리가 되지 않은 원소들 삭제
    while min_heap and not visit[min_heap[0][1]]:
        heapq.heappop(min_heap)
    while max_heap and not visit[max_heap[0][1]]:
        heapq.heappop(max_heap)

    # heap에 원소가 존재할 경우, 최대, 최소값 출력
    if min_heap and max_heap:
        print(-max_heap[0][0], min_heap[0][0])
    else:
        print('EMPTY')

---

전체코드

import sys
import heapq

input = sys.stdin.readline

max_heap = []       # 최대힙
min_heap = []       # 최소힙

visit = [False] * 1_000_001     # 방문 처리, False = 삭제, True = 미삭제

n = int(input())

for _ in range(n):

    t = int(input())
    for i in range(t):

        # 연산과 원소 받음
        op, num = map(str, input().split())
        num = int(num)

        # input 일때
        if op == 'I':

            # 최대힙, 최소힙에 index번호와 함께 삽입
            heapq.heappush(min_heap, (num, i))
            heapq.heappush(max_heap, ((-1)*num, i))

            # 원소있음, 미삭제 처리
            visit[i] = True
        
        # delete 일때
        elif op == 'D':
            
            # 최소값 삭제
            if num == -1:
                
                # 상대힙에 의해 삭제되었을 경우, 해당원소 계속해서 삭제
                while min_heap and not visit[min_heap[0][1]]:
                    heapq.heappop(min_heap)
                
                # 배열안에 원소 존재시, 삭제처리하고 pop
                if min_heap:
                    visit[min_heap[0][1]] = False
                    heapq.heappop(min_heap)
            
            elif num == 1:
                while max_heap and not visit[max_heap[0][1]]:
                    heapq.heappop(max_heap)
                if max_heap:
                    visit[max_heap[0][1]] = False
                    heapq.heappop(max_heap)

    # 삭제처리가 되지 않은 원소들 삭제
    while min_heap and not visit[min_heap[0][1]]:
        heapq.heappop(min_heap)
    while max_heap and not visit[max_heap[0][1]]:
        heapq.heappop(max_heap)

    # heap에 원소가 존재할 경우, 최대, 최소값 출력
    if min_heap and max_heap:
        print(-max_heap[0][0], min_heap[0][0])
    else:
        print('EMPTY')

 

시간초과 코드

import sys
import heapq

input = sys.stdin.readline
heap = []

n = int(input())
for _ in range(n):

    t = int(input())
    for _ in range(t):
        op, num = map(str, input().split())
        num = int(num)

        if op == 'I':
            # heapq.heappush(heap, num)
            heap.append(num)
        
        elif op == 'D':

            if num == 1:
                heapq.heapify(heap)
                if len(heap) != 0:
                    heap.remove(heap[len(heap) - 1])

            elif num == -1:
                heapq.heapify(heap)
                if len(heap) != 0:
                    heap.remove(heap[0])

    if len(heap) == 0:
        print('EMPTY')
    
    else:
        print(max(heap), min(heap))

---

heap을 어느정도 구현할 수 있다고 생각했는데, 많이 부족함을 느낄 수 있었던 문제였습니다. 확실히 자료구조를 잘 다뤄야 시간 초과의 늪에서 벗어날 수 있음을 뼈저리게 느꼈습니다. 아직 구현하는 데에 집중을 하는데 더 효율적이고 시간복잡도를 줄이기 위한 방법을 많이 생각해야 할 것 같습니다.

설명의 오류나, 궁금하신점은 언제든 피드백해주시면 감사하겠습니다 ^~^