BOJ. 7662 이중 우선순위 큐 (Python)

[ 문제 ]

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

7662번: 이중 우선순위 큐

[ 나의 풀이 ] 

🔸 접근 방법

최소힙, 최대힙을 선언하고 연산이 I인 경우에 값을 해당 연산이 몇번째인지 값과 함께 저장한다.

값을 제거하면 removed 리스트에서 제거한 값임을 표시한다. 최소값, 최대값을 제거하고 만약 제거한 index의 값이면 제거하고 다시 최소값, 최대값을 찾고 제거한다.

 

🔸 풀이 코드

# 7662 이중 우선순위 큐
# 221206

import sys, heapq
input = sys.stdin.readline

# 테스트 케이스 정수 T
T = int(input())
for _ in range(T):
    # 적용할 연산의 개수 k
    k = int(input())
    # 연산을 저장할 최소힙MinQ, 최대힙MaxQ
    MinQ = list()
    MaxQ = list()
    
    # 제거한 것 체크할 리스트
    removed = [False] * k

    # k번 연산을 반복
    for k_idx in range(k):
        msg, n = input().split()
        # 연산이 'I'인 경우
        if msg == 'I':
            heapq.heappush(MinQ, (int(n), k_idx))
            heapq.heappush(MaxQ, (-int(n), k_idx))
        # 연산이 'D'인 경우
        else:
            # 최댓값을 삭제하는 연산
            if n == '1':
                while MaxQ:
                    # MaxQ에서 가장 작은 값 => 최댓값
                    maxNum, idx = heapq.heappop(MaxQ)
                    if removed[idx] == False:
                        removed[idx] = True
                        break
                    else: continue                                          
            # 최솟값을 삭제하는 연산
            else:
                while MinQ:
                    # MinQ에서 가장 작은 값 => 최솟값
                    minNum, idx = heapq.heappop(MinQ)
                    if removed[idx] == False:
                        removed[idx] = True
                        break
                    else: continue                                          

    # 최댓값, 최솟값 선언
    maxNum, minNum = None, None

    # MaxQ가 존재한다면
    while MaxQ:
        # 최댓값 찾기
        maxNum, idx = heapq.heappop(MaxQ)
        # 지우지 않은 값이라면 최댓값 저장
        if removed[idx] == False:
            break
        # 지운 값이라면 최댓값 초기화
        else: 
            maxNum = None
            continue
                           
    # MinQ가 존재한다면
    while MinQ:
        # 최솟값 찾기
        minNum, idx = heapq.heappop(MinQ)
        # 지우지 않은 값이라면 최솟값 저장
        if removed[idx] == False:
            break
        # 지운 값이라면 최솟값 초기화
        else: 
            minNum = None
            continue

    if maxNum and minNum :
        print(-maxNum, minNum)
    else:
        print('EMPTY')

 

[ pair의 풀이 ]

🔸 접근 방법

pair도 똑같은 방법으로 풀었다 😀

 

🔸 풀이 코드

import heapq
import sys
input = sys.stdin.readline

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

    # 리스트 생성
    max_arr = list()
    min_arr = list()
    answer = ''

    # 출력 조건 변수 생성
    check = [False for _ in range(a)]

    for idx in range(a):
        k, n = input().split()
        # 처음 문자가 I 일 때, 리스트에 숫자 추가
        if k == 'I':            
            # max 리스트와 min 리스트에 각각 숫자 추가
            heapq.heappush(max_arr, (-int(n), idx))
            heapq.heappush(min_arr, (int(n), idx))

            # 해당 인덱스 위치에 숫자가 있음을 확인
            check[idx] = True

        # 처음 문자가 D 일 때
        else:
            # 최소값 제거
            if int(n) == -1:
                # max에서 지워졌던 값을 제거하기 위한 반복 과정
                while min_arr and not check[min_arr[0][1]]:
                    heapq.heappop(min_arr)
                # min을 지우고 해당 index를 False로 변경하여 지웠다는 것을 체크
                if min_arr:
                    check[min_arr[0][1]] = False
                    heapq.heappop(min_arr)
            # 최대값 제거
            else:
                # min에서 지워졌던 값을 제거하기 위한 반복 과정
                while max_arr and not check[max_arr[0][1]]:
                    heapq.heappop(max_arr)
                # max를 지우고 해당 index를 False로 변경하여 지웠다는 것을 체크
                if max_arr:
                    check[max_arr[0][1]] = False
                    heapq.heappop(max_arr)

    # 마지막으로 한번 더 수행하여 지워졌던 값을 제거
    while min_arr and not check[min_arr[0][1]]:
        heapq.heappop(min_arr)
    while max_arr and not check[max_arr[0][1]]:
        heapq.heappop(max_arr)

    if max_arr and min_arr:
        answer = str(-max_arr[0][0]) + ' '
        answer += str(min_arr[0][0])
    else:
        answer = 'EMPTY'    

    print(answer)

 

pair 의 github : https://github.com/Ui-Seok