[백준/파이썬] 7662번 이중 우선순위 큐 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 7662번 이중 우선순위 큐
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.
정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.
Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.
- 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요
코드
import sys;read=sys.stdin.readline
import heapq
result=[]
for T in range(int(read())):
visited=[False]*1_000_001
minH,maxH=[],[]
for i in range(int(read())):
s=read().split()
if s[0]=='I':
heapq.heappush(minH,(int(s[1]),i))
heapq.heappush(maxH,(-int(s[1]),i))
visited[i]=True
elif s[1]=='1':
while maxH and not visited[maxH[0][1]]:heapq.heappop(maxH)
if maxH:
visited[maxH[0][1]]=False
heapq.heappop(maxH)
else:
while minH and not visited[minH[0][1]]:heapq.heappop(minH)
if minH:
visited[minH[0][1]]=False
heapq.heappop(minH)
while minH and not visited[minH[0][1]]:heapq.heappop(minH)
while maxH and not visited[maxH[0][1]]:heapq.heappop(maxH)
result.append(f'{-maxH[0][0]} {minH[0][0]}'if maxH and minH else'EMPTY')
print('\n'.join(result))
설명
자료 구조 중 이중 우선순위 큐를 구현하여 푸는 문제입니다.
문제에서 이중 우선순위 큐란, 이중 큐(deque, 데크)와 우선순위 큐를 합한 개념으로 설명합니다.
우선, 우선순위 큐는 파이썬에서 heapq 라이브러리의 형태로 힙을 구현한 것을 응용하면 됩니다. 우선순위 큐의 대표적인 구현체가 바로 힙이죠.
파이썬 힙큐 모듈 공식 문서를 참고하시면 편합니다. 간단하게 설명하자면, 따로 정의된 클래스라기 보다는 기존의 iterable한 객체를 응용합니다. 힙의 내부 연산 구조는 모듈에서 모두 지원해주기 때문에 따로 구현할 필요가 없습니다.
힙의 구조는 일반적인 완전 이진 트리에서, 최대 힙이냐 최소 힙이냐에 따라 각 서브트리의 루트 노드가 가져야 할 값이 최대값이냐, 최소값이냐가 결정되는 트리입니다.
다만, 파이썬의 힙큐의 경우 기본적으로 최소힙만을 지원하기 때문에, 최대힙을 이용하려면 기교를 부려야합니다.
여러가지 방법이 있겠지만, 가장 간단한 방법으로는 -1을 곱하면 될 것입니다. 이유는 설명할 필요가 없으리라 생각하고, 삽입시에 -1을 곱한상태로 넣고, 결과값이 필요할 때 다시 -1을 한번 더 곱해주면 될 것 입니다.
여기까지 하면 최소 힙과 최대힙은 문제없이 구현했습니다. 그런데, 아직 해결하지 못한 문제가 있습니다. 바로 ‘이중’이라는 키워드죠. 따로 구현해봤자 따로 동작하면 값이 달라져버릴진대, 무슨 소용이 있겠습니까? 저희는 구현한 최소힙과 최대힙을 동기화 시켜주어야 합니다.
이를 위해, 힙에 푸시할 때 입력받은 값 외에도 특수한 값을 하나 더 넣습니다. 바로 식별자id죠. 각 노드를 유일하게 구분할 식별자가 필요합니다. 이는 반복문이 몇 번 수행되었는지를 가리키는 변수 i를 유일성을 만족시키는 id로 사용할 수 있습니다. 튜플의 형태로 넣어줍시다. 파이썬의 튜플 비교연산은 우선 첫 번째 원소를 기준으로 판단하기 때문에 id를 두 번째 원소로 넣어주면 힙의 구동에도 아무런 문제가 없습니다.
그렇다면, 이런 식별자를 넣어준 이유가 무엇인가? 궁긍하실 수 있습니다. 앞서 언급했듯, 이는 동기화를 위한 작업입니다. 우선, 삽입 연산 시에는 따로 동기화가 필요 없을 것입니다. 각각 삽입만 해주면 끝일테죠. 하지만, 삭제 연산 시에는 각자 차이가 발생합니다. 최소힙은 최소값만 pop할 수 있지, 최대값을 바로 빼는 방법이 없습니다. 그 반대도 마찬가지입니다. 따라서, 삭제연산 시, 먼저 이 id를 기준으로 해당 노드가 다른 힙에서 삭제된 노드인가 아닌가를 판단합니다. 이미 삭제된 노드일경우 삭제되지 않은 노드가 나올 때 까지 모두 버립니다. 이후 삭제 대상 노드가 등장하면 삭제합니다. 이를 위해 각 id별로 활성상태를 기록하는 플래그 리스트인 visited를 사용합니다.
모든 연산이 끝난 후에도 이런 쓰레기 노드들이 들어있을 수 있습니다. 때문에, 결과를 내기 전 쓰레기 노드를 모두 비우고, 각 힙의 첫번째 원소의 값을 출력합니다.
댓글남기기