BOJ 7662 이중 우선순위 큐 - java

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

7662번: 이중 우선순위 큐

 

 

문제

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

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

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

 

풀이

처음엔 PriotyQueue 2개를 이용해 하나는 오름차순, 나머지는 내림차순으로

 

PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>();
PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(Collections.reverseOrder());

 

구현하여, 돌렸으나 queue.remove(Object n)의 시간으로 인해 시간초과로 실패.

 

TreeMap 자료구조를 이용해서 품 (트리 Comparator에 의해 정렬이 되며, log (n) 시간으로 정렬이 가능하며 최소 최대값은 firstKey() 와 lastKey() 메소드를 이용해 접근 가능함.)

 

기본적으로 Map인터페이스를 같이 상속받고 있으므로 기본적인 메소드의 사용법 자체는 HashMap과 동일하게 사용

D, I Command(명령)에 따른 조건을 통해 나눠서 풀었으며, 동일한 값이 들어오는 경우를 대비해 Value 값을 증가함.삭제 시에는 반대로 해당 값에서 -1을 해줌.

 

Insert 명령어

treeMap.put(num, treeMap.getOrDefault(num, 0)+1);

 

Delete 명령어

treeMap.put(max, treeMap.get(max)-1);

treeMap.put(min, treeMap.get(min)-1);

 

전체 소스코드