[백준] 7662 이중 우선순위 큐 (Python 파이썬)

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

7662번: 이중 우선순위 큐

자세한 설명은 위 링크를 참고해주세요.

---

풀이 과정

우선순위 큐 두개를 놓고 풀었다.

일반 우선순위큐와는 다르게 최대값과 최소값 모두를 빼올 수 있는 우선순위큐를 만들어야 하기 때문에

하나는 최소값용 우선순위큐

다른 하나는 최대값용 우선순위큐를 만든다.

이 때, 주의해야 할 점은 최소값 우선순위큐에서 값을 제거한다면

마찬가지로 최대값 우선순위큐에서도 제거를 해서 두 우선순위의 상태를 맞춰주어야 한다는 점이다.

 

처음에 접근했던 방식은 최대값을 구할 때는 최댓값 우선순위큐에서 pop을 하고

최소값 우선순위큐의 마지막 원소를 삭제하는 식으로 구현을 했다.

 

하지만 heapq자체가 정렬되어 있는 상태가 아니기 때문에(Heap구조를 유지하지만 정렬되어있진 않음)

이 방식은 틀린 방식이었다.

 

그렇다고 PriorityQueue를 사용하자니, 첫 원소를 제외하고는 따로 삭제할 수 있는 방법이 없었다.

 

그래서 각각의 원소에 ID를 부여하여, 해당 원소가 삭제된 원소인지 아닌지를 판별하여

두 큐의 상태를 맞춰주었다.

 

예를 들어, 3이라는 원소가 삽입되었다가 최소값 큐에서 삭제된 상태라면

최대값 큐에서도 삭제된 상태여야 하기 때문에

 

최대값에서 검사를 할 때, 해당 원소의 상태가 True인지 False인지를 판별하여 실제 존재하는 원소인지 아닌지를 알 수 있게 되는 것이다.

import heapq

t = int(input())

for i in range(t):
    k = int(input())
    q1, q2 = [], []
    visited = [False] * k

    for j in range(k):
        com, num = input().split()

        if com == 'I':
            heapq.heappush(q1, (int(num), j))
            heapq.heappush(q2, (-int(num), j))
            visited[j] = True

        else:
            if num == '1':
                while q2 and not visited[q2[0][1]]:
                    heapq.heappop(q2)
                if q2:
                    visited[q2[0][1]] = False
                    heapq.heappop(q2)
            else:
                while q1 and not visited[q1[0][1]]:
                    heapq.heappop(q1)
                if q1:
                    visited[q1[0][1]] = False
                    heapq.heappop(q1)

    while q1 and not visited[q1[0][1]]:
        heapq.heappop(q1)
    while q2 and not visited[q2[0][1]]:
        heapq.heappop(q2)

    if not q1 or not q2:
        print("EMPTY")
    else:
        a = -q2[0][0]
        b = q1[0][0]
        print("%d %d" % (a, b))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !