https://www.acmicpc.net/problem/7662
7662번: 이중 우선순위 큐
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적
www.acmicpc.net
설명
1️⃣ Priority Queue
Priority Queue란?
- 큐(Queue)는 우선순위를 결정하고, 우선순위가 높은 원소가 먼저 나간다.
- 우선순위 큐는 힙을 이용하여 구현한다.
- 데이터 삽입: 우선순위를 기준으로 최대힙, 최소힙 구성한다.
- 데이터 삭제: 루트 노드 제거 후 빈 루트 노드 위치에 맨 마지막 노드를 삽입하고 아래로 내려가면서 적절한 자리를 찾아 옮긴다.
- 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다. -> 시간 복잡도 O(NlogN)
import java.util.PriorityQueue; //import
//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>();
//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
값 추가
priorityQueue.add(1); // priorityQueue 값 1 추가
priorityQueue.add(2); // priorityQueue 값 2 추가
priorityQueue.offer(3); // priorityQueue 값 3 추가- add: 큐가 꽉차면, IllegalStateException 예외 발생
- offer: 추가 실패를 의미하는 false 반환
값 삭제
priorityQueue.remove(); // priorityQueue에 첫번째 값을 반환하고 제거, 비어있다면 Exception
priorityQueue.poll(); // priorityQueue에 첫번째 값을 반환하고 제거, 비어있다면 null
priorityQueue.clear(); // priorityQueue에 초기화- remove: 큐가 비어있으면, IllegalStateException 예외 발생
- poll: 큐가 비어있으면, null 반환
값 확인
priorityQueue.peek(); // priorityQueue의 첫번째 값 참고 -> 가장 우선순위가 높은 것 반환
문제 풀이
- 큰 값과 작은 값으로 정렬해야 하기 때문에 PriorityQueue를 두개 사용한다.
- minQueue: 작은 값을 기준으로 정렬
- maxQueue: 큰 값을 기준으로 정렬 -> Collections.reverseOrder()를 사용하여 반대로 정렬한다.
- 값 제거는 어떻게 하는 것이 좋을까?
- remove 함수를 사용한다. ➡️ 순차적으로 접근하다 equals == true 일 때 제거하므로 O(N)의 시간복잡도를 갖으므로, ⚡️시간초과 발생⚡️
- Map을 이용해 숫자와 해당 숫자의 갯수를 저장한다.
- insert
map.getOrDefault 사용하여, 이미 key가 있다면 -> 매핑된 값에 +1하고, key가 없다면 -> 0을 반환하고 +1 해서 갯수를 저장한다. - delete
- queue에서 poll 하여 값을 꺼낸다.
- 해당 값을 Map에서 찾는다.
- 존재하지 않는다면 -> 반복문으로 찾는다.
- 존재한다면 -> 해당 key의 개수를 변경한다.
- map의 value를 감소시키고, put한다.
- 1이라면 map에서 삭제한다.
- insert
+) getOrDefault(Object key, V DefaultValue)
- key: 값을 가져와야 하는 요소의 키
- defaultValue: 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본값
=> 찾는 key가 존재하면 해당 key에 매핑된 값을 반환하고, 그렇지 않으면 디폴트 값이 반환된다.
2️⃣ TreeMap
TreeMap이란?
- 이진트리를 기반으로, 키와 값이 저장된 Map, Entry를 저장한다.
- 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 오름차순으로 정렬된다.
- 이진탐색트리의 문제점을 보완한 레드 블랙 트리(Red-Black Tree)로 이루어졌다. 레드 블랙 트리는 트리에 값이 한쪽으로 치우쳐있을 때, 비효율적인 퍼포먼스를 보완하기 위해 나왔다. 부모노드보다 작은 값을 가지는 노드는 왼쪽으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 한쪽으로 치우치지 않도록 균형을 맞춰준다.
문제 풀이
- 첫번째 원소와 마지막 원소는 firstKey()와 lastKey() 함수로 찾는다.
- 숫자와 해당 숫자가 저장된 갯수를 저장하고 있으므로, 삭제할 때는 기존 value에 -1한 것을 더해준다.
코드
priority Queue
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int T, k;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
k = Integer.parseInt(br.readLine());
Map<Integer, Integer> map = new HashMap<>();
PriorityQueue<Integer> minQueue = new PriorityQueue<>(); // 오름차순
PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순
for (int i = 0; i < k; i++) {
String[] input = br.readLine().split(" ");
String operation = input[0];
int n = Integer.parseInt(input[1]);
if (operation.equals("I")) {
map.put(n, map.getOrDefault(n, 0) + 1);
minQueue.add(n);
maxQueue.add(n);
} else {
if (map.size() == 0) {
continue;
}
PriorityQueue<Integer> queue = n == 1 ? maxQueue : minQueue;
removeMap(queue, map);
}
}
if (map.size() == 0) {
sb.append("EMPTY").append("\n");
} else {
int num = removeMap(maxQueue, map);
sb.append(num + " " + (map.size() > 0 ? removeMap(minQueue, map) : num)).append("\n");
}
}
System.out.println(sb);
}
static int removeMap(PriorityQueue<Integer> queue, Map<Integer, Integer> map) {
int num;
// queue에는 해당 값이 존재하지 않을 수 있기 때문에 반복하면서 꺼낸다.
while (true) {
num = queue.poll();
int cnt = map.getOrDefault(num, 0);
if (cnt == 0) {
continue;
}
if (cnt == 1) {
map.remove(num);
} else {
map.put(num, cnt - 1);
}
break;
}
return num;
}
}TreeMap
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class Main {
static int T, k;
static TreeMap<Integer, Integer> treeMap;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
k = Integer.parseInt(br.readLine());
treeMap = new TreeMap<>();
for (int j = 0; j < k; j++) {
String[] str = br.readLine().split(" ");
String operation = str[0];
int n = Integer.parseInt(str[1]);
if (operation.equals("I")) {
treeMap.put(n, treeMap.getOrDefault(n, 0) + 1);
} else {
// 사이즈가 0이면 continue
if (treeMap.size() == 0) {
continue;
}
int num;
if (str[1].equals("-1")) { // 최솟값 삭제
num = treeMap.firstKey();
} else { // 최댓값 삭제
num = treeMap.lastKey();
}
if (treeMap.put(num, treeMap.get(num) - 1) == 1) {
treeMap.remove(num);
}
}
}
if (treeMap.isEmpty()) {
sb.append("EMPTY").append("\n");
} else {
sb.append(treeMap.lastKey() + " " + treeMap.firstKey()).append("\n");
}
}
System.out.println(sb);
}
}
Reference
https://coding-factory.tistory.com/603
반응형
