[Python] BOJ no.7662 이중 우선순위 큐

문제 링크

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

7662번: 이중 우선순위 큐

문제 설명

이번 문제는 우선순위 큐에 어떤 정수값을 append하되, 일반적인 heapq가 지원하지 않는 큐에서 가장 큰 값도 제거할 수 있는 기능이 추가된 프로그램을 만드는 것이 목표이다. 

 

먼저 test case 개수를 받고 test case마다 지시사항 입력값을 받는다.

 

지시사항 입력값은 "I 숫자" 또는 "D 1", "D -1"로 I는 큐에 숫자를 대입하는 지시, D는 최소나 최대를 큐에서 제거하는 지시사항이다.

 

---

풀이 #1

import heapq, sys
input = sys.stdin.readline
t = int(input())

for _ in range(t):
    k = int(input())

    q = []
    for _ in range(k):
        order, num = input().split()
        num = int(num)
        if order == 'I':
            q.append(num)
        else:
            if len(q) > 0:
                if num == -1:
                    heapq.heapify(q)
                    heapq.heappop(q)
                else:
                    q = [-x for x in q]
                    heapq.heapify(q)
                    heapq.heappop(q)
                    q = [-x for x in q]
        
    if len(q) == 0:
        print('EMPTY')
    else:
        print(max(q), min(q))

첫 번째 풀이는 우선순위 큐 하나만을 사용해서 시도해보았다. 큐에 입력값을 넣는 경우에는 list에 단순하게 숫자를 넣어주듯 append로 추가해주었다. 다만 큐에서 어떤 값을 제거하는 "D"가 입력되었을 때만 두 가지 케이스로 나누어 진행해주었다.

 

1. 최소값을 제거하는 경우 (if num == -1) → 가지고 있던 list를 heapify 메서드를 통해 힙정렬을 수행하고 heappop 메서드를 사용해 최솟값을 제거해준다.

2. 최댓값을 제거하는 경우 (if num == 1)  → 가지고 있던 list의 원소들을 모두 음수로 변환해주고 힙정렬 수행뒤 heappop 메서드를 사용해 최솟값(사실은 최댓값)을 제거해준다. 이후 다시 양수로 변환해준다.

 

^@^ 짜증 ^@^

 

 

풀이 # 2

결국 못참고 다른 사람의 풀이를 보고 다시 코드를 작성했다. 코드를 보니 아이디어는 단순했다. 내가 그 아이디어를 떠올리지 못했을 뿐....

 

import heapq, sys
input = sys.stdin.readline
t = int(input())

for _ in range(t):
    k = int(input())

    q_max = []
    q_min = []
    visited = [False] * k
    for j in range(k):
        order, num = input().split()
        num = int(num)
        if order == 'I':
            heapq.heappush(q_max, (-num, j))
            heapq.heappush(q_min, (num, j))
            visited[j] = True
        else:
            if num == 1:
                while q_max and not visited[q_max[0][1]]:
                    heapq.heappop(q_max)
                if q_max:
                    visited[q_max[0][1]] = False
                    heapq.heappop(q_max)
            else:
                while q_min and not visited[q_min[0][1]]:
                    heapq.heappop(q_min)
                if q_min:
                    visited[q_min[0][1]] = False
                    heapq.heappop(q_min)
    while q_max and not visited[q_max[0][1]]:
        heapq.heappop(q_max)       
    while q_min and not visited[q_min[0][1]]:
        heapq.heappop(q_min)
    
    if q_min and q_max:
        print(-q_max[0][0], q_min[0][0])
    else:
        print('EMPTY')

 

첫 번째 풀이와 다른 점은 우선순위 큐를 두 개 사용한다는 것인데, 첫 번째 풀이에서 나는 사실상 두 개의 우선순위 큐를 쓴 것과 다름없기 때문에 로직은 거의 유사하다. (사실 정답 풀이를 보고도 어떤 부분에서 내 풀이가 시간적으로 안좋은 코드인지 잘 모르겠다.. \_/)

 

내 코드와 다른점은 곳곳에 들어가 있는 while 문이다.

 

먼저 최소힙, 최대힙, 두 개의 우선순위 큐를 만들어준다. 최대힙은 넣을 정수에 -1을 곱해 추가해주면 된다!

그리고 큐에 추가해줄 때 visited에서 사용할 j라는 index를 추가해준다.

 

이 후 visited가 해당 index에서 True인 경우는 최소힙, 최대힙 두 우선순위 큐에서 해당 정수가 살아있다는 의미이고 False라면 그 정수가 둘 중 하나의 힙 이상에서 삭제되었다는 의미이다.

 

while은 그 기능을 하는 부분이다.

 

while에서 q가 존재하면서 가장 앞부분(힙에서 pop을 할 때 나올 부분)의 index인 j값을 visited로 확인해보면 두 힙에 모두 살아있는지, 그렇지 않은지 알 수 있다. 때문에 while로 계속해서 확인하면서 이미 삭제된 정수에 대해서는 계속해서 날리고 살아있는 정수에 대해서만 삭제를 진행해준다.

 

이 과정을 통해 최소힙, 최대힙에서는 계속해서 최신화가 가능하면서 삭제와 추가가 원활히 이루어질 수 있는 프로그램을 완성할 수 있다.

 

---

Reference

https://chaewsscode.tistory.com/m/138

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

서채리님 감사함다.