BOJ_7662_이중 우선순위 큐(Java)
[Gold IV] 이중 우선순위 큐 - 7662
성능 요약
메모리: 451072 KB, 시간: 2648 ms
분류
자료 구조, 우선순위 큐, 트리를 사용한 집합과 맵
제출 일자
2024년 9월 25일 05:27:29
문제 설명
이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.
정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.
Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.
입력
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)가 주어진다. 이어지는 k 줄 각각엔 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n이 주어진다. ‘I n’은 정수 n을 Q에 삽입하는 연산을 의미한다. 동일한 정수가 삽입될 수 있음을 참고하기 바란다. ‘D 1’는 Q에서 최댓값을 삭제하는 연산을 의미하며, ‘D -1’는 Q 에서 최솟값을 삭제하는 연산을 의미한다. 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제됨을 유념하기 바란다.
만약 Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다. Q에 저장될 모든 정수는 -231 이상 231 미만인 정수이다.
출력
출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값을 출력하라. 두 값은 한 줄에 출력하되 하나의 공백으로 구분하라. 만약 Q가 비어있다면 ‘EMPTY’를 출력하라.
문제풀이
O(N) 으로 최대 최소 우선순위큐에서 찾아 삭제하면 시간초과가 발생, 지울 값을 map별로 저장해 key를 통해 O(1)로 찾아 삭제.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
public static void main(String[] args) throws Exception {
new Main().solution();
}
static PriorityQueue<Integer> ASC_PQ = new PriorityQueue<Integer>();
static PriorityQueue<Integer> DESC_PQ = new PriorityQueue<Integer>(Collections.reverseOrder());
static int T, N;
public void solution() throws Exception {
// br = new BufferedReader(new InputStreamReader(System.in));
br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(br.readLine());
while (T-- > 0) {
ASC_PQ.clear();
DESC_PQ.clear();
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String mode = st.nextToken();
int num = Integer.parseInt(st.nextToken());
switch (mode) {
case "I": {
ASC_PQ.add(num);
DESC_PQ.add(num);
break;
}
case "D": {
if (!ASC_PQ.isEmpty()) {
int deletedNum = (num == 1) ? deleteMax() : deleteMin();
}
break;
}
}
}
if (ASC_PQ.size() < 1)
System.out.println("EMPTY");
else if (ASC_PQ.size() == 1)
System.out.println(ASC_PQ.poll());
else {
System.out.print(DESC_PQ.poll() + " ");
System.out.print(ASC_PQ.poll() + " ");
System.out.println("시간초과");
}
}
bw.close();
br.close();
}
// num == 1
private int deleteMax() {
int deletedNum = DESC_PQ.poll();
ASC_PQ.remove(deletedNum);
return deletedNum;
}
// num == -1
private int deleteMin() {
int deletedNum = ASC_PQ.poll();
DESC_PQ.remove(deletedNum);
return deletedNum;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static StringBuilder sb;
static StringTokenizer st;
public static void main(String[] args) throws Exception {
new Main().solution();
}
static PriorityQueue<Integer> ASC_PQ = new PriorityQueue<Integer>();
static PriorityQueue<Integer> DESC_PQ = new PriorityQueue<Integer>(Collections.reverseOrder());
static Map<Integer, Integer> map; // 숫자 개수
static int T, N;
public void solution() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
while (T-- > 0) {
ASC_PQ.clear();
DESC_PQ.clear();
map = new HashMap<>();
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String mode = st.nextToken();
int num = Integer.parseInt(st.nextToken());
switch (mode) {
case "I": {
ASC_PQ.add(num);
DESC_PQ.add(num);
map.put(num, map.getOrDefault(num, 0) + 1);
// System.out.println(map);
break;
}
case "D": {
if (!map.isEmpty()) {
if (num == 1) {
delete(DESC_PQ);
} else {
delete(ASC_PQ);
}
}
break;
}
}
}
if (map.isEmpty()) {
sb.append("EMPTY\n");
} else {
int max = delete(DESC_PQ);
sb.append(max).append(" ");
// 하나뿐인지
if (!map.isEmpty()) {
int min = delete(ASC_PQ);
sb.append(min);
// System.out.println("min : " + min);
}
else {
sb.append(max);
// System..println("max : " + max);
}
sb.append("\n");
}
}
System.out.print(sb);
br.close();
}
private int delete(Queue<Integer> pq) {
int deleteNum;
while (true) {
deleteNum = pq.poll();
int cnt = map.getOrDefault(deleteNum, 0);
// System.out.println("cnt : " + cnt);
if (cnt == 0) continue;
if (cnt == 1) map.remove(deleteNum);
else map.put(deleteNum, cnt - 1);
break;
}
return deleteNum;
}
}