[백준] 이중 우선순위 큐 - GOLD IV 7662
[Programmers] 이중 우선순위 큐 - LEVEL 3
접근
- 우선순위 큐
풀이
우선순위 큐처럼 우선순위를 가지고 내부가 정렬되며 양쪽으로 데이터를 삭제할 수 있는 자료구조를 구현하는 문제이다. 익숙한 기억이 프로그래머스를 뒤져보니 역시나 풀었던 문제로 프로그래머스에선 LV 3에 해당하는 문제였다. 옛날에 프로그래머스에서 풀었을 때 remove를 사용해 풀었던 다른 사람의 코드가 있었다. 우선순위 큐에도 remove라는 메서드가 있구나 하며 기억에 남아 remove를 사용해 풀어봤지만 백준에서는 시간초과라는 결과가 나왔다. 그래서 차근차근 이중 우선순위 큐를 구현해 보기로 했다.
private static class PriorityDeque {
private final PriorityQueue<Integer> minQue;
private final PriorityQueue<Integer> maxQue;
private final Map<Integer, Integer> map;
public PriorityDeque() {
this.minQue = new PriorityQueue<>();
this.maxQue = new PriorityQueue<>(Collections.reverseOrder());
this.map = new HashMap<>();
}우선 이중 우선순위큐를 구현하기 위해 최대 힙과 최소 힙 이렇게 두 개를 사용해 구현할 예정이다. map의 경우 한쪽에서 삭제가 일어나면 다른 쪽은 알지 못하기에 값을 추적하기 위해 사용한다.
public void add(Integer num) {
minQue.offer(num);
maxQue.offer(num);
map.merge(num, 1, Integer::sum);
}삽입 메서드이다. 양쪽 우선순위 큐에 삽입을 해주고 맵에 값을 저장한다. 원소가 현재 큐 내부에 몇 개가 들어있는지를 확인하기 위해 사용하는 것이다.
public Integer removeMin() {
if (minQue.isEmpty())
return null;
while (!map.containsKey(minQue.peek())) {
minQue.poll();
if(minQue.isEmpty())
return null;
}
Integer value = map.get(minQue.peek()) - 1;
if (value == 0) {
map.remove(minQue.peek());
} else {
map.put(minQue.peek(), value);
}
Integer min = minQue.poll();
return min;
}최솟값을 삭제하는 메서드이다. 큐가 비어있다면 null을 반환하고 맵을 뒤져서 내가 삭제할 원소가 현재 큐에 들어있는 원소인지를 확인한다. 한쪽에서 삭제한 원소를 다른 쪽에선 어떤 원소가 삭제되었는지 알 수 없기 때문에 맵에 존재하는 원소가 실질적으로 존재하는 원소라고 생각하면 된다. 맵에 존재하는 원소가 나올 때까지 없어진 원소를 버려주고 삭제할 원소가 나오면 맵에서 해당 원소의 개수를 하나 줄여주고 반환한다. 개수가 0이 될 경우 맵에서 삭제한다.
public Integer removeMax() {
if(maxQue.isEmpty()) return null;
while (!map.containsKey(maxQue.peek())) {
maxQue.poll();
if(maxQue.isEmpty())
return null;
}
Integer value = map.get(maxQue.peek()) - 1;
if (value == 0) {
map.remove(maxQue.peek());
} else {
map.put(maxQue.peek(), value);
}
Integer max = maxQue.poll();
return max;
}최댓값을 삭제하는 메서드로 최솟값을 삭제하는 메서드에서 최소 힙 대신 최대 힙을 사용하는 것 말고는 다른 점이 없다.
public int[] getResult() {
if (map.isEmpty()) return null;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (Integer i : map.keySet()) {
min = Math.min(min, i);
max = Math.max(max, i);
}
int[] res = {max, min};
return res;
}연산이 끝난 후 최댓값과 최솟값 출력을 위해서 만든 메서드이다. 맵의 키셋을 순회하여 최댓값과 최솟값을 찾아 반환한다. 이 문제의 경우 HashMap대신 TreeMap을 사용한다면 결과 반환 부분을 짧은 코드로 마무리할 수 있다.
public int[] getResult() {
if (map.isEmpty()) return null;
int[] res = {map.lastKey(), map.firstKey()};
return res;
}TreeMap은 내부적으로 균형 잡힌 이진 탐색 트리인 레드-블랙 트리(Red-Black Tree)를 사용하여 데이터를 저장한다. 그렇기 때문에 TreeMap은 키를 항상 정렬된 상태로 가지고 있어 가장 처음 위치한 키와 가장 마지막 키를 반환하여 최대 최솟값을 편하게 반환받을 수 있으나 TreeMap의 경우 삽입, 삭제, 조회에 대한 시간 복잡도가 O(log n)으로 평균적으로 O(1)의 복잡도를 가지는 HashMap에 비해 좋지 않다. 그래서 이 문제처럼 빈번히 연산이 많이 일어나는 경우 메모리 사용량과 시간 효율이 HashMap에 비해 떨어져 주어지는 연산의 개수가 더 늘어난다면 TreeMap을 사용해선 원하는 시간을 맞추지 못할 가능성이 있다.
public boolean isEmpty() {
return map.isEmpty();
}큐가 비어있을 시 D 연산은 무시되므로 Empty 체크를 위한 메서드도 하나 만들어 주었다.
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int k = Integer.parseInt(br.readLine());
PriorityDeque priorityDeque = new PriorityDeque();
for (int j = 0; j < k; j++) {
String[] commands = br.readLine().split(" ");
switch (commands[0]) {
case "D":
if (commands[1].equals("1")) {
if (!priorityDeque.isEmpty()) {
priorityDeque.removeMax();
}
} else {
if (!priorityDeque.isEmpty()) {
priorityDeque.removeMin();
}
}
break;
case "I":
priorityDeque.add(Integer.parseInt(commands[1]));
}
}메인 부분 코드이다. 연산을 입력받고 각 연산에 맞춰 내용을 수행해 주는 내용이다.
if (priorityDeque.getResult() == null) {
bw.write("EMPTY\n");
continue;
}
int[] result = priorityDeque.getResult();
bw.write(result[0] + " " + result[1]+"\n");수행이 끝난 뒤 큐가 비었다면 EMPTY를 출력해 주고 비어있지 않다면 최댓값과 최솟값을 출력해 준다.
전체 코드
import java.io.*;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Main {
private static class PriorityDeque {
private final PriorityQueue<Integer> minQue;
private final PriorityQueue<Integer> maxQue;
private final Map<Integer, Integer> map;
public PriorityDeque() {
this.minQue = new PriorityQueue<>();
this.maxQue = new PriorityQueue<>(Collections.reverseOrder());
this.map = new HashMap<>();
}
public void add(Integer num) {
minQue.offer(num);
maxQue.offer(num);
map.merge(num, 1, Integer::sum);
}
public Integer removeMin() {
if (minQue.isEmpty())
return null;
while (!map.containsKey(minQue.peek())) {
minQue.poll();
if(minQue.isEmpty())
return null;
}
Integer value = map.get(minQue.peek()) - 1;
if (value == 0) {
map.remove(minQue.peek());
} else {
map.put(minQue.peek(), value);
}
Integer min = minQue.poll();
return min;
}
public Integer removeMax() {
if(maxQue.isEmpty()) return null;
while (!map.containsKey(maxQue.peek())) {
maxQue.poll();
if(maxQue.isEmpty())
return null;
}
Integer value = map.get(maxQue.peek()) - 1;
if (value == 0) {
map.remove(maxQue.peek());
} else {
map.put(maxQue.peek(), value);
}
Integer max = maxQue.poll();
return max;
}
public int[] getResult() {
if (map.isEmpty()) return null;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (Integer i : map.keySet()) {
min = Math.min(min, i);
max = Math.max(max, i);
}
int[] res = {max, min};
return res;
}
public boolean isEmpty() {
return map.isEmpty();
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int k = Integer.parseInt(br.readLine());
PriorityDeque priorityDeque = new PriorityDeque();
for (int j = 0; j < k; j++) {
String[] commands = br.readLine().split(" ");
switch (commands[0]) {
case "D":
if (commands[1].equals("1")) {
if (!priorityDeque.isEmpty()) {
priorityDeque.removeMax();
}
} else {
if (!priorityDeque.isEmpty()) {
priorityDeque.removeMin();
}
}
break;
case "I":
priorityDeque.add(Integer.parseInt(commands[1]));
}
}
if (priorityDeque.getResult() == null) {
bw.write("EMPTY\n");
continue;
}
int[] result = priorityDeque.getResult();
bw.write(result[0] + " " + result[1]+"\n");
}
bw.flush();
bw.close();
br.close();
}
}'알고리즘 > 코딩테스트-백준' 카테고리의 다른 글
| [백준] IOIOI JAVA (0) | 2024.09.22 |
|---|---|
| [백준] 회의실 배정 JAVA (1) | 2024.09.14 |
| [백준] Z JAVA (2) | 2024.09.11 |
| [백준] 헌내기는 친구가 필요해 JAVA (0) | 2024.09.10 |
| [백준] DSLR JAVA (0) | 2024.09.09 |