자료구조 - 우선순위 큐

우선순위 큐 "Priority Queue"란 말 그대로 우선순위가 존재하는 큐이다.

큐는 FIFO특성을 가지는 자료구조로 먼저 들어온 것을 먼저 내보내는 구조이고 우선순위 큐는 이러한 큐의 특성에 우선순위를 부여하여 

우선순위에 대해 먼저 내보내는 특성을 가지고 있다.

 

Java에서도 이러한 Queue나  Priority Queue를 지원하는 라이브러리가 있다.

아래의 코드와 함께 예시를 보겠지만, 간단하게 add를 통해 입력받고 peek를 통해 우선순위가 제일 높은 값을 출력하고

remove를 통해 출력과 삭제를 할 수 있다. 

 

우선순위 큐 라이브러리를 사용해 보기위해서 "백준 1655번 가운데를 말해요" 문제를 풀어보았다.

해당 문제는 다음과 같다. 

 

문제를 푼 코드는 아래와 같다.

입력값이 주어질때마다의 가운데 값을 구해야하는 건데 우선순위 큐인 Priority Queue를 사용하여 전체 값의 반을 기준으로 

작은 값들의 모임인 minQueue를 선언하고, 큰 값들의 모임인 maxQueue를 선언하여

minQueue에서 제일 큰 값과 maxQueue에서 제일 작은 값을 비교하여 다른 queue로 옮겨줄지 정한다.

maxQueue와 minQueue의 크기를 다시 비교하여 minQueue의 사이즈가 maxQueue의 사이즈보다 하나 크거나 같지 않은 모든 경우에 대해 더 큰 사이즈의 큐에서 하나 remove해와 다른 큐로 값을 옮겨준다. 

 

우선순위 큐는