[Java] 백준(골드-4) 7662번 - 이중 우선순위 큐
문제 풀이
이번 문제는 문제명인 이중 우선순위 큐를 이용하면 시간 초과가 발생하기에 TreeMap 자료구조를 이용해 풀어야 한다.
아이디어 도출
별 다른 생각없이 최소 힙, 최대 힙을 구현한 2개의 우선순위 큐를 이용하여 풀었지만, 큐의 삭제 연산 remove() 메서드를 수행할 때 시간복잡도가 O(n)이기에 시간초과가 발생했다.
최소 힙, 최대 힙 우선순위 큐 2개를 이용한 풀이 - 시간초과 발생
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
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
// 1. 이중 우선순위 큐를 구현하기 위해 최소 힙, 최대 힙인 우선순위 큐 2개를 활용한다.
// 2. I 명령이면 N을 삽입하고, D 1 명령이면 큐의 최댓값 제거, D -1 명령이면 큐의 최솟값을 제거한다.
// 3. D 명령 수행시 큐가 비었다면 무시하고 진행한다.
// 4. 큐에 저장되는 정수의 범위는 -2^31 부터 2^31까지 이기에 long형 타입을 사용해야 한다.
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
int T = Integer.parseInt(br.readLine());
while(T --> 0) {
// 최솟값을 기준으로 정렬할 최소 힙 우선순위 큐 선언
PriorityQueue<Long> min_q = new PriorityQueue<>();
// 최댓값을 기준으로 정렬할 최대 힙 우선순위 큐 선언
PriorityQueue<Long> max_q = new PriorityQueue<>(new Comparator<Long>() {
@Override
public int compare(Long o1, Long o2) {
if(o1 > o2) {
return -1;
}
else if(o1 < o2) {
return 1;
}
else {
return 0;
}
}
});
int K = Integer.parseInt(br.readLine());
while(K --> 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
long N = Long.parseLong(st.nextToken());
// cmd == I
if(cmd.equals("I")) {
min_q.offer(N);
max_q.offer(N);
}
// cmd == D
else {
// 최댓값 제거일 경우 최대 힙(max_q)에서만 제거
if(N == 1) {
if(max_q.isEmpty()) continue;
long target = max_q.poll();
min_q.remove(target);
}
// 최솟값 제거일 경우 최소 힙(min_q)에서만 제거
else if(N == -1) {
if(min_q.isEmpty()) continue;
long target = min_q.poll();
max_q.remove(target);
}
}
}
/**
* 큐가 비어있다면 "EMPTY"를 출력하고
* 비어있지 않다면, 최댓값과 최솟값을 공백을 두고 출력한다.
*/
if(min_q.isEmpty() && max_q.isEmpty()) {
bw.write("EMPTY"+"\n");
} else {
bw.write(max_q.peek()+ " " + min_q.peek() + "\n");
}
}
}
}
}
이를 위해, 시간 초과가 발생하는 큐를 사용하는 것이 아니라 원소 추가 및 삭제에 O(logN)의 시간복잡도를 가지는 TreeMap를 이용하여 풀게 되었다. TreeMap을 활용해 풀 수 있는 아이디어를 다음과 같이 생각해보았다.
I N명령일 경우, N을 TreeMap에 Key로, N의 빈도수(개수)를 Value로 삽입한다.- D 명령일 경우 TreeMap이 비어있다면 D 연산을 무시하고 넘어간다.
D 1명령일 경우, TreeMap의 마지막 값(lastKey())을 제거한다.D -1명령일 경우, TreeMap의 첫번째 값(firstKey())을 제거한다.
TreeMap 자료구조는 오름차순 정렬이 기본으로 설정되어있다. 또한, firstKey() 메서드와 lastKey() 메서드가 존재한다. firstKey() 메서드는 Map의 첫번째 키를, lastKey() 메서드는 Map의 마지막 키를 가져올 수 있다.
결국, TreeMap의 두 메서드를 통해 이중 우선순위 큐에서 서로의 큐의 삭제연산을 할 때의 비용을 절감하여 시간 초과를 해결할 수 있었다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
// 1. 이중 우선순위 큐를 구현하기 위해 최소 힙, 최대 힙인 우선순위 큐 2개를 활용한다.
// 2. I 명령이면 N을 삽입하고, D 1 명령이면 큐의 최댓값 제거, D -1 명령이면 큐의 최솟값을 제거한다.
// 3. D 명령 수행시 큐가 비었다면 무시하고 진행한다.
// 4. 큐에 저장되는 정수의 범위는 -2^31 부터 2^31까지 이기에 long형 타입을 사용해야 한다.
// 5. D 명령 수행시 큐 remove() 연산을 수행하게 되면 시간초과가 발생한다.
// 6. 원소의 추가, 삭제 이후에 정렬 상태를 유지하는데 O(logN)의 시간복잡도를 가지는 TreeMap 자료구조를 이용해 풀어야 한다.
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
int T = Integer.parseInt(br.readLine());
while(T --> 0) {
// 최소힙과 최대힙의 원소와 개수를 담을 TreeMap 선언
TreeMap<Long, Integer> tm = new TreeMap<>();
int K = Integer.parseInt(br.readLine());
while(K --> 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
long N = Long.parseLong(st.nextToken());
// cmd == I
if(cmd.equals("I")) {
tm.put(N, tm.getOrDefault(N, 0)+1);
}
// cmd == D
else {
// TreeMap이 비어있다면 D 연산은 무시한다.
if(tm.isEmpty()) continue;
// 최댓값 제거
if(N == 1) {
// 최댓값 key
long last = tm.lastKey();
// 1개밖에 없다면 Map에서 제거
if(tm.get(last) == 1) {
tm.remove(last);
continue;
}
// 2개 이상이라면 개수 1개 차감
tm.put(last, tm.get(last)-1);
}
// 최솟값 제거
else if(N == -1) {
// 최솟값 key
long first = tm.firstKey();
// 1개밖에 없다면 Map에서 제거
if(tm.get(first) == 1) {
tm.remove(first);
continue;
}
// 2개 이상이라면 개수 1개 차감
tm.put(first, tm.get(first)-1);
}
}
}
/**
* 큐가 비어있다면 "EMPTY"를 출력하고
* 비어있지 않다면, 최댓값과 최솟값을 공백을 두고 출력한다.
*/
if(tm.isEmpty()) {
bw.write("EMPTY"+"\n");
} else {
bw.write(tm.lastKey()+ " " + tm.firstKey() + "\n");
}
}
}
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.