Baekjoon 7662번 이중 우선순위 큐

문제

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

걸린 시간

02 : 25 : 46 실패

풀이

PyPy3

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    T = int(input())

    result = []

    for _ in range(0, T):
        k = int(input())
        dic = {}
        for _ in range(0, k):
            tmp = input().strip().split()
            command = tmp[0]
            value = int(tmp[1])

            if command == 'I':
                if dic.get(value, -1) == -1:
                    dic[value] = 0
                else:
                    dic[value] += 1
            elif command == 'D':
                if len(dic) != 0:
                    if value == 1:
                        ma = max(dic)
                        if dic[ma] == 0:
                            del(dic[ma])
                        else:
                            dic[ma] -= 1
                    elif value == -1:
                        mi = min(dic)
                        if dic[mi] == 0:
                            del(dic[mi])
                        else:
                            dic[mi] -= 1
        if len(dic) == 0:
            result.append("EMPTY")
        else:
            result.append(str(max(dic)) + ' ' + str(min(dic)))

    for i in result:
        print(i)

하나의 딕셔너리만을 이용한 풀이로 최대 최소값을 구하는데 O(n) 만큼의 시간이 걸려 Python3 으로는 통과하지 못했다.

효율적인 풀이

Python3

from collections import deque
import bisect
import sys
input = sys.stdin.readline

if __name__ == "__main__":
    T = int(input())

    result = []

    for _ in range(0, T):
        k = int(input())
        d = deque()
        dic = {}
        for _ in range(0, k):
            tmp = input().strip().split()
            command = tmp[0]
            value = int(tmp[1])

            if command == 'I':
                if dic.get(value, -1) == -1:
                    dic[value] = 1
                    bisect.insort_left(d, value)
                else:
                    dic[value] += 1
            elif command == 'D':
                if not d:
                    pass
                else:
                    if value == 1:
                        if dic.get(d[-1], -1) == 1:
                            dic.pop(d[-1])
                            d.pop()
                        else:
                            dic[d[-1]] -= 1
                    elif value == -1:
                        if dic.get(d[0], -1) == 1:
                            dic.pop(d[0])
                            d.popleft()
                        else:
                            dic[d[0]] -= 1
        if len(dic) == 0:
            result.append("EMPTY")
        else:
            result.append(str(d[-1]) + ' ' + str(d[0]))

    for i in result:
        print(i)

딕셔너리와 정렬된 덱을 이용한 풀이이다.

입력받은 값를 덱에 오름차순을 유지하며 삽입하는 것이 관건인데 파이썬 내장함수인 bisect 을 이용하면 쉽게 해결할 수 있다.

이진 탐색으로 값이 들어갈 위치를 찾고 insert 메소드로 해당 위치에 삽입하는 작업을 insort_left 함수로 편리하게 구현해두었기 때문이다.

문제의 제목이 이중 우선순위 큐 인 만큼 최대-최소 힙을 구현하여 풀이하는 방법도 알아봐야겠다.

참고

• 백준 7662 - 뒤늦게 시작하는 기술 블로그
• Min-Max Heap