[백준/Python] (G4) 7662- 이중 우선순위 큐

이중 우선순위 큐 성공다국어

한국어   

 

7662번: 이중 우선순위 큐

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

6 초

256 MB

66501

14953

11023

21.853%

문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)가 주어진다. 이어지는 k 줄 각각엔 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n이 주어진다. ‘I n’은 정수 n을 Q에 삽입하는 연산을 의미한다. 동일한 정수가 삽입될 수 있음을 참고하기 바란다. ‘D 1’는 Q에서 최댓값을 삭제하는 연산을 의미하며, ‘D -1’는 Q 에서 최솟값을 삭제하는 연산을 의미한다. 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제됨을 유념하기 바란다.

만약 Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다. Q에 저장될 모든 정수는 -231 이상 231 미만인 정수이다.

출력

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값을 출력하라. 두 값은 한 줄에 출력하되 하나의 공백으로 구분하라. 만약 Q가 비어있다면 ‘EMPTY’를 출력하라.

예제 입력 1 복사

2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333

예제 출력 1 복사

EMPTY
333 -45

---

큐에 대한 정의를 알아보자.

 

큐는 파이프에 네모난 나무조각을 집어넣는것으로 생각할 수 있다.

파이프의 양쪽 끝을 각각 front, rear로 두고, rear에 나무조각에 번호를 1번부터 매겨 집어 넣는다.

이렇게 하면 나무조각이 들어가다가 길이 이상으로 들어가면 front쪽으로 나올것이고, 나무조각은 1번부터 나올것이다.

이러한 자료 구조를 갖는것이 큐(Queue)구조다.

 

큐는 FIFO(First In First Out)구조를 가지고 있다.

 

이러한 정보를 이미 알고 있었기 때문에 위의 문제를 큐를 이용하여 풀이 하려고 했다.

 

문제에서 제시해둔 조건을 보면 연산은 I, D 두가지이고, I 4라는 연산이 들어오면 큐에 4를 집어 넣는다. 

그리고 D 1이면 최댓값 , D -1이면 최솟값을 삭제한다.

 

따라서 처음에 이런식으로 코딩을 진행했다.

#7662 이중 우선순위 큐 
import sys
from collections import deque

t = int(sys.stdin.readline())

for i in range(t):
    q = deque()
    k = int(sys.stdin.readline())
    for j in range(k):
        op = list(sys.stdin.readline().split())
        if op[0] == 'I':
            q.append(int(op[1]))
        else: #D인 경우
            if len(q) == 0: #큐가 비었을 경우 무시
                continue
            else:
                if op[1] == '1': #최댓값 한개 삭제
                    q.remove(max(q))
                else: #최솟값 한개 삭제
                    q.remove(min(q))
        
        # print(q, len(q))
        
    if len(q) == 0:
        print("EMPTY")
    else:
        print(max(q), min(q))

 

풀이도 맞았다 생각했고 예제도 잘 나왔기 때문에 제출했는데 시간초과가 떴다.

 

사실 max함수는 이미 시간 복잡도가 꽤 긴걸 알고 있었다.

이유는 최댓값을 계산 하려면 모든 원소를 비교해야하기 때문에 O(n)의 시간 복잡도를 가지고 있기 때문이다.

 

정렬과 탐색 알고리즘에 관련해서는 아래의 글에 정리를 해뒀다.

https://freeedeveloper.tistory.com/entry/%EC%9D%B4%EC%BD%94%ED%85%8CPython-4%EC%9E%A5-%EC%A0%95%EB%A0%AC-%EB%AA%A8%EB%93%A0%EA%B2%83

[이코테/Python] 4장 정렬 - 모든것.

https://freeedeveloper.tistory.com/entry/%EC%9D%B4%EC%BD%94%ED%85%8CPython-5%EC%9E%A5-%ED%83%90%EC%83%89

[이코테/Python] 5장 - 탐색

 

하지만 이것만으로 풀 순 없었고, 우선순위큐라는 자료구조를 알아야한다.

 

우선순위큐는 힙 자료구조로 나타낼 수 있다.

 

힙은 완전 이진트리 자료구조다. 여러개의 자료중에서 특정 값을 빠르게 찾기 위해 고안되었다.

말만 들어도 왜 우선순위 큐를 힙으로 표시해야되는지 감이 왔다.

위는 힙에 대한 그림이고, 최대힙을 나타낸다. 최소힙은 작은것이 루트노드가 된다. 

 

이렇게 하여 파이썬의 heapq 라이브러리를 임포트 하고 코드를 작성하면 다음과 같다.

#7662 이중 우선순위 큐 
import heapq
import sys

t = int(sys.stdin.readline())

for i in range(t):
    k = int(sys.stdin.readline())
    maxheap = []
    minheap = []
    
    for j in range(k):
        op = list(sys.stdin.readline().split())
        
        if op[0] == 'I':
            heapq.heappush(maxheap, -int(op[1]))
            heapq.heappush(minheap, int(op[1]))
            
        else:
            if op[1] == '1': #최댓값 삭제
                if maxheap: #리스트가 비어있으면 false반환
                    heapq.heappop(maxheap)
                
            else:
                if minheap:
                    heapq.heappop(minheap)
                    
        print(maxheap, minheap)
    
    if len(minheap) == 0:
        print("EMPTY")
    else:
        print(-maxheap[0], minheap[0])

기본적으로 파이썬에서는 최소힙만 제공하기 때문에 최대힙을 구현하려면 요소를 마이너스 부호를 넣어서 저장하고, 나중에 꺼낼땐 다시 부호를 바꿔 출력하면 된다.

 

하지만 위의 코드에서는 pop과정에서 오류가 있다.

두 힙 모두 같은 요소가 삭제되어야 하지만 연산을 진행하다가 보면 서로 값이 동기화가 되지 않는다.

즉, 최소힙에서 값을 pop하면 최대힙에서 해당하는 값을 pop해줘야한다.

 

그래서 구글링을 통해 구조를 학습하였고 다음과 같이 코드를 수정했다.

 

최종코드

#7662 이중 우선순위 큐 
import heapq
import sys

t = int(sys.stdin.readline())

for i in range(t):
    k = int(sys.stdin.readline())
    
    maxheap = []
    minheap = []
    check = [1] * (k+1)
    
    for j in range(k):
        op = list(sys.stdin.readline().split())
        
        if op[0] == 'I':
            heapq.heappush(maxheap, (-int(op[1]),j))
            heapq.heappush(minheap, (int(op[1]),j))
            
        else:
            if op[1] == '1': #최댓값 삭제
                if maxheap: #리스트가 비어있으면 false반환
                    check[heapq.heappop(maxheap)[1]] = 0 #반대쪽도 삭제해주기 위해 변수에 저장
            else:
                if minheap:
                    check[heapq.heappop(minheap)[1]] = 0
                
            while minheap and check[minheap[0][1]] == 0: #리스트가 비어있지 않고 조건에 맞는다면 
                heapq.heappop(minheap) #반대쪽도 삭제
                    
            while maxheap and check[maxheap[0][1]] == 0:
                heapq.heappop(maxheap)
                
    if len(minheap) == 0:
        print("EMPTY")
    else:
        print(-maxheap[0][0], minheap[0][0])

값을 저장할 때, 집합 연산으로 값과 저장된 순서를 저장한다. (양쪽 힙 모두 저장해야한다. 최대힙은 어떤 수가 오든 부호를 바꿔 저장한다.)

 

이후 D 연산이 들어오게 되면 미리 준비해둔 check리스트의 값을 0으로 바꿔주고, 해당 수가 삭제 예정이라는 신호를 준다.

 

pop을 한 뒤 while문을 이해하기 힘들었는데 while의 조건은 

minheap 부분 즉, 조건으로 리스트가 오면 리스트를 끝까지 탐색하거나, 리스트가 빌 때 까지 반복하게 된다. 또한 and뒤의 조건을 보면 리스트의 값이 0이라면 true를 반환하게 되어 heappop연산이 루트 노드만 삭제되는게 아니라 특정 인덱스의 값을 삭제한다는것을 알았다.

 

이 문제를 풀기 위해서는 다른 이해보다 while문의 조건으로 인해 pop연산을 인덱스별로 적용시킬 수 있다는 점을 꼭 알아야될것 같지만 두루뭉술하게 감이 오는 상태라 조금 더 이해해봐야 할 필요가 있을 것 같다.