[BOJ][Python]7662번 풀이

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

7662번: 이중 우선순위 큐

import heapq
import sys
ssr = sys.stdin.readline

t = int(ssr())
for _ in range(t):
    minh, maxh = [], []
    k = int(ssr())
    visited = [False for _ in range(k)]
    for i in range(k):
        c = ssr().split()
        if c[0] == 'I':
            heapq.heappush(minh, (int(c[1]), i))
            heapq.heappush(maxh, (-int(c[1]), i))
        else:
            if c[1] == '1':
                if len(maxh) == 0:
                    continue
                else:
                    while maxh:
                        if visited[maxh[0][1]] == True:
                            heapq.heappop(maxh)
                        else:
                            a = heapq.heappop(maxh)
                            visited[a[1]] = True
                            break
            else:
                if len(minh) == 0:
                    continue
                else:                
                    while minh:
                        if visited[minh[0][1]] == True:
                            heapq.heappop(minh)
                        else:
                            a = heapq.heappop(minh)
                            visited[a[1]] = True
                            break
    while maxh:
        if visited[maxh[0][1]] == True:
            heapq.heappop(maxh)
        else:
            break
    while minh:
        if visited[minh[0][1]] == True:
            heapq.heappop(minh)
        else:
            break
    if len(minh) == 0 or len(maxh) == 0:
        print('EMPTY')
    else:
        print(-maxh[0][0],minh[0][0])

개인적으로 조금 주먹구구식으로 푼 것 같아 마음이 아픈 문제입니다만 아직 힙을 잘 쓰지 못하다 보니 뭔가 더 줄이지는 못하겠더라구요. 일단은 위 코드를 기준으로 설명을 드려보겠습니다.

 

일단 해당 문제는 '이중 우선 순위 큐'라는 문제입니다. 지난 번에 최대 힙, 최소 힙 문제를 풀면서 우선 순위 큐에 대해서 알아봤었죠. 기억이 안나는 분들을 위해 간단하게 설명을 드리자면 우선 순위 큐는 큐 자료형 속에 있는 원소들이 우선 순위를 기준으로 정렬되어 있는 자료형이라고 할 수 있겠습니다. 원래 큐라는 자료형은 먼저 들어온게 먼저 나가는 특징을 갖고 있는데요. 그런 큐의 특성에 우선 순위를 적용해서 '우선 순위가 높은 원소가 먼저 나가는' 메커니즘을 갖는 자료형이 우선 순위 큐라고 할 수 있겠습니다. 그리고 이런 우선 순위 큐를 구현하기 위해 만들어진 자료형 중에 힙(heap)이라는 자료형이 있습니다(우선 순위 큐를 구현하는 방법이 힙 밖에 없는 것은 아닙니다). 힙은 완전 이진 트리의 구조로 해당 큐 안에서 원소들은 부모 노드와 자식 노드 사이에서 우선 순위를 기준으로 연결이 되고 이 경우 기준에 따라 다르지만(최소 or 최대) 근본적으로는 부모 노드가 자식 노드보다 우선 순위가 높게 정렬된다는 특징이 있습니다. 예를 들어 숫자가 작은게 우선 순위가 높다면 무조건 부모 노드는 자식 노드보다 작은 숫자여야 한다는 약속에 따라 정렬이 되고 맨 위에 있는 노드는 해당 원소들 중에서 가장 작은 숫자가 됩니다(숫자가 큰게 우선 순위가 높다면 최대값이 맨 위에 오겠죠). 이런 특징이자 장점을 이용해서 우선 순위 큐는 최솟값 또는 최댓값을 구하는 경우에 있어서 굉장히 빠른 속도를 자랑합니다(다만 모든 자료가 우선 순위대로 정렬되는 것은 아닌게, 힙은 형제 노드 사이에서는 우선 순위가 적용되지 않고 부모 자식간에만 적용이 된다는 사실을 잊으시면 안됩니다).

 

설명이 길어졌습니다만 파이썬에서는 위와 같은 우선 순위 큐를 구현하는 모듈인 heapq라는 모듈을 지원합니다. 다만 heap은 최소 힙 또는 최대 힙만 쓸 수 있으니 지금 처럼 최대 최소를 동시에 우선 순위로 가질 수는 없겠죠(사실 이 부분은 제가 잘 모르는 것일 수도 있습니다). 그래서 저는 최소 힙과 최대 힙을 둘 다 만들어서 원소를 추가해야할 경우에는 두 군데 다 추가해주고 원소를 뺄 경우에는 이미 뺐던 원소인지 아닌지 체크하기 위해 그래프 문제에서 사용하던 방문 처리를 해줬습니다. 다만 해당 문제의 경우 중복된 숫자가 있을 수도 있다는 언급과 입력 가능한 정수의 범위가 32비트 정수이기 때문에 하던대로 숫자로 했다간 방문 처리 리스트를 만들다 시간 초과가 날 것 같으니 명령의 순서를 함께 저장해서 나중에 pop을 할 때 해당 순서를 방문 처리 함으로서 해결했습니다. 물론 이미 방문했던 녀석들은 최소 힙, 최대 힙 둘 다 지워져야 하므로 반복문으로 지워줬습니다. 출력하기 전에도 혹시 남아있을 안지워진 녀석들을 한 번 더 지워준 다음 주어진 조건에 맞게 출력해주면 됩니다.

 

사실 문제 자체가 엄청 어려운 문제는 아니라고 생각합니다. 힙을 몇 번 써보신 분들이라면 최소 최대 각각 만들어서 써야겠구나 하고 바로 감을 잡으셨을 것 같기도 하구요. 숫자 범위도 음수도 있고 크기도 크니까 명령에 인덱스를 붙여서 써먹어라 하고 생각이 들 정도로 노골적인 힌트도 있구요. 다만 저는 힙 자체를 많이 써보질 않아서 그런가 하면서도 확신이 안서는 문제이긴 했습니다. 한 줄 쓰고 머리로도 생각해보고 디버깅도 해보고 할 정도로 쭉쭉 풀어나가지 못하고 수정에 수정을 했던 문제가 아닐까 싶네요.