P7662

[baekjoon-7662] 이중 우선순위 큐

시간초과 이슈

처음에는 Programmers 이중우선순위큐 문제 풀이 방법과 동일하게 Priority Queue를 두 개 선언해서 풀었다. 그랬더니 시간초과 이슈가 났다. 이 문제는 시간복잡도를 줄이기 위해 이진 트리의 자료구조가 필요하며, 최댓값과 최솟값 둘 모두에 빠른 접근이 가능해야 한다. 문제를 해결하기 위해 자바 API의 몇몇 자료구조를 찾아보았다.

• Priority Queue : Heap으로 구현되어 있어 데이터 접근이 비교적 빠르지만, 한 쪽으로만 데이터를 삭제할 수 있어 최댓값과 최솟값 모두에 접근하려면 minHeap과 maxHeap 두 개를 선언하여 풀어야 하고, 한 쪽에서 삭제 연산이 일어날 경우 다른 쪽에도 삭제해주어야 한다.
• Deque : 덱처럼 양 옆에서 데이터를 삭제할 수 있었으면 좋겠는데, 앞뒤로 정렬이 되어있어야 한다. 매번 정렬을 하기엔 O(N)으로 시간복잡도가 크다.
• TreeMap : 이진 트리를 기반으로 하며, Map 인터페이스를 구현하여 key-value 형태로 데이터를 저장한다. TreeMap은 객체를 저장할 때 key를 기준으로 오름차순 정렬하여 저장한다. 따라서 TreeMap 자료구조가 이 문제를 해결하기에 적합하다고 생각하였다.

TreeMap

참고 : [Java] 자바 TreeMap 사용법 & 예제 총정리

TreeMap은 이진 탐색 트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree) 로 구현되어 있다. 일반적인 이진 탐색 트리는 트리 높이만큼의 시간복잡도가 발생하는데, 값이 전체 트리에 잘 분산되어 있다면 괜찮으나 트리가 한 쪽으로 쏠릴 경우 매우 비효율적이다. 이 문제를 보완한 자료구조가 레드-블랙 트리이며, 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한 쪽으로 쏠리지 않도록 한다.

따라서 정렬된 상태로 Map을 유지할 때 효율적이며, 정렬 때문에 추가/삭제 연산 성능은 HashMap보다 떨어진다.

TreeMap을 이용한 문제 풀이

• key로 삽입된 데이터를, value로 그 데이터의 갯수를 넣어 관리하였다.
• 최솟값 삭제 연산은 map.firstKey()로, 최댓값 삭제 연산은 map.lastKey()로 수행하였다.