[코딩테스트][백준] 🔥 백준 7662번 "이중 우선순위 큐" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 60분

import heapq

for tc in range(int(input())):
    n=int(input())
    qMin=[]
    qMax=[]
    numDict=dict()
    for _ in range(n):
        oper,num=map(str,input().split())
        if oper=='I':
            heapq.heappush(qMin,int(num))
            heapq.heappush(qMax,-int(num))
            if num not in numDict:
                numDict[num]=0
            numDict[num]+=1
        elif oper=='D':
            if int(num)==-1:
                while qMin and (str(qMin[0]) not in numDict or numDict[str(qMin[0])]<=0):
                    heapq.heappop(qMin)
                if qMin:
                    minValue=heapq.heappop(qMin)
                    numDict[str(minValue)]-=1
                    if numDict[str(minValue)]<=0:
                        del numDict[str(minValue)]
            else:
                while qMax and (str(-qMax[0]) not in numDict or numDict[str(-qMax[0])]<=0):
                    heapq.heappop(qMax)
                if qMax:
                    maxValue=-heapq.heappop(qMax)
                    numDict[str(maxValue)]-=1
                    if numDict[str(maxValue)]<=0:
                        del numDict[str(maxValue)]
    if len(numDict.keys())==0:
        print("EMPTY")
    else:
        print(max(map(int,numDict.keys())),min(map(int,numDict.keys())))

이중 우선순위 큐 구현! 🔄🔢

이중 우선순위 큐처럼 동작하는 큐를 만들어쓰거나 이와 같은 형태로 다른 자료구조를 합쳐서 다루는 문제인것 같다. 처음에는 파이썬만의 반칙으로 heapq.nlargest를 쓰려고 하였으나 시간초과가 나길래 다른 자료형으로 바꾸어 풀었다.

먼저 문제에서 필요한 데로 최소 힙과, 최대 힙으로 쓸 것을 만들어 두고 이것을 관리하기 위해 해당 원소의 갯수를 담을 dict을 하나 두었다. 먼저 삽입 연산을 할 때는 이 dict에 없으면 추가해주고 +1을 해주고 나머지 heapq 두개에도 삽입을 하여준다.

이제 중요한 것을 삭제 연산을 할 때 인데, 이 때 가장 작은 원소나 가장 큰 원소를 제거해주기 전에 heapq에는 남아있으나 dict에는 없는 즉, 실존하지 않는 원소들을 앞에서부터 전부 제거해준다. 이 때 while문을 사용하여 dict에 없거나 dict에 있어도 0보다 작은 없는 모든 원소를 제거해주면 된다. 그런 다음 heapq에서 우선순위에 따라 꺼내주고 dict에서 해당 원소를 -1해주면 된다. 이 때 방금 -1을 한 원소가 0보다 같거나 작아지면 없는 원소이므로 dict에서도 삭제해주면 된다.

정답 출력 시에는 현재 최종 상태는 heapq가 아니라 dict에 기록되고 있으므로 dict을 기준으로 해주는데 key값들이 하나도 없다면 EMPTY를 출력하고 그렇지 않다면 key값들이 str형으로 되어있기 때문에 int형으로 mapping해서 최댓값과 최솟값을 출력하여 주었다.

이렇게 Python으로 백준의 "이중 우선순위 큐" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊