[백준 7662번] 파이썬 - 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

 

 

 

# 조건

• 이중 우선순위 큐는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료구조
• 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제
• 데이터를 삽입하는 연산과 데이터를 삭제하는 연산 사용
• 데이터를 삭제하는 연산은 우선순위가 가장 높은 것을 삭제하는 것과 우선순위가 가장 낮은 것을 삭제하는 것으로 나뉜다.
• Q에 적용할 연산의 개수 k <= 1,000,000
• I n은 정수 n을 Q에 삽입
• D -1 은 Q에서 최솟값 삭제
• D 1 은 Q에서 최댓값을 삭제

 

# 접근 방법

• 하나의 정보를 가지고 2개의 heapq를 다루는 문제이다.
• PriorityQueue와 heapq 모듈은 최소 우선순위만을 지원하기 때문에 최대 값을 pop해줄 수가 없다.
• 따라서, 최소힙과 최대힙을 같이 만들어주며, 딕셔너리를 이용해 들어온 횟수를 기록해준다.
• 최소, 최대힙에서 명령어에 맞게 값을 빼준다.
• 이 때, 최소 힙과 최대 힙의 동기화가 필요하기 때문에 -> 이미 제거된 값이 들어있을 수도 있기 때문에
• flag 변수를 이용하여, 유효한 값을 제거할 때까지 반복해서 heappop 해준다.
• 결과 출력 전에 정렬을 통하여 최대, 최소값을 뽑아준다.
• 모든 연산이 끝난 후 최소 최대힙의 값이 유효한지를 검증한 후 최대값과 최소값을 출력해준다.

 

 

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappush, heappop  
  
  
T = int(input())  
for tc in range(T):  
    N = int(input())  
    min_q = []  
    max_q = []  
    is_valid = {}  
    flag = True  
    for i in range(N):  
        # 명령어와 숫자를 따로 받아준다.  
        a, b = input().split()  
        if a == 'I':  
	        # 최소, 최대힙을 만들어주고, 딕셔너리에 들어온 기록 남겨주기
            heappush(min_q, int(b))  
            heappush(max_q, -int(b))  
            if int(b) in is_valid:  
                is_valid[int(b)] += 1  
            else:  
                is_valid[int(b)] = 1  
        else:  
			# 최소힙에서 값 추출
            if b == '-1' and min_q:  
                # heappop(min_q)  
                # 최대힙에서 pop한 값이 남아있을 수도 있다.
                # 따라서, is_valid의 밸류값이 0 보다 큰 경우가 나올 때 까지 반복
                while flag and min_q:  
                    a = heappop(min_q)  
                    if is_valid[a] <= 0:  
                        continue  
                    else:  
                        is_valid[a] -=1  
                        flag = False  
                flag = True  
  
  
            elif b == '1' and max_q:  
                # heappop(max_q)  
                # 마찬가지로 최소힙에서 추출한 값이 남아있을 수도 있으므로
                # is_valid의 밸류값이 0보다 큰 경우가 나올 때 까지 반복
                while flag and max_q:  
                    b = heappop(max_q)  
                    if is_valid[-b] <= 0:  
                        continue  
                    else:  
                        is_valid[-b] -= 1  
                        flag = False  
                flag = True  
  
  
    cnt = 0  
    # 정렬을 통해 최대 최소를 뽑아줄 준비를 한다.
    max_q.sort()  
    min_q.sort()  
    # 값이 유효하면 추출
    for j in range(len(max_q)):  
        if is_valid[-max_q[j]] > 0:  
            print(-max_q[j], end=' ')  
            cnt = 1  
            break  
    for i in range(len(min_q)):  
        if is_valid[min_q[i]] > 0:  
            print(min_q[i], end=' ')  
            cnt = 1  
            break  
	# 값을 추출하지 못하였다면 empty 출력
    if cnt == 0:  
        print('EMPTY')