[PS] 99ํด๋ฝ ์ฝํ ์คํฐ๋ 10์ผ์ฐจ TIL (์ด์ค์ฐ์ ์์ํ)
ํ๊ทธ: 99ํด๋ฝ, PS, TIL, ์ฝ๋ฉํ ์คํธ์ค๋น, ํญํด99, ํ(Heap)
์นดํ ๊ณ ๋ฆฌ: PS
๋ฌธ์
ํ์ด
์ฒซ๋ฒ์งธ ํ์ด
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int[] solution(String[] operations) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
for (String command : operations) {
if (command.contains("I")) {
maxHeap.add(Integer.valueOf(command.split(" ")[1]));
minHeap.add(Integer.valueOf(command.split(" ")[1]));
} else if (command.equals("D 1")) {
minHeap.remove(maxHeap.poll());
} else {
maxHeap.remove(minHeap.poll());
}
}
int[] result = new int[2];
result[0] = maxHeap.peek() == null ? 0 : maxHeap.peek();
result[1] = minHeap.peek() == null ? 0 : minHeap.peek();
return result;
}
}
๋ฌธ์ ์์ ์๊ตฌํ๋ ๊ฒ์ ์ต์๊ฐ ๋๋ ์ต๋๊ฐ์ ๋ฝ๋ ํ๋์ ๊ฒฝ์ฐ๊ฐ ์๋๋ผ, ์กฐ๊ฑด์ ๋ฐ๋ผ ์ฐ์ ์์ ํ์์ ์ต๋๊ฐ์ ๋ฝ๋์ง, ์ต์๊ฐ์ ๋ฝ๋์ง ํด์ผ ํ๋ค.
PriorityQueue
์๋ ์ต์๊ฐ๊ณผ ์ต๋๊ฐ์ ์ ๋ณํ๋ ๋ฉ์๋๊ฐ ์๊ณ , ๋จ์ง ์์ฑ ์ ์ ๋ฌํด ์ฃผ๋ ํ๋ผ๋ฏธํฐ์ ๋ฐ๋ผ ํ ์์ ์์๋ฅผ ์ ๋ ฌํ๋ค.
๋ง์ฝ ํ๋ผ๋ฏธํฐ ์์ด ์์ฑํ๊ฒ ๋๋ฉด PriorityQueue
๋ ์์ฐ ์์(natural ordering) ๋ฅผ ๋ฐ๋ฅธ๋ค. ์ฆ, PriorityQueue
์ ์ ์ฅ๋ ๊ฐ์ฒด๋ค์ ๊ธฐ๋ณธ์ ์ผ๋ก ๊ฐ์ฒด์ Comparable
์ธํฐํ์ด์ค์ compareTo
๋ฉ์๋์ ์ํด ์ ๋ ฌ๋๋ค.
์ซ์๋ ์ค๋ฆ์ฐจ์์ผ๋ก, ๋ฌธ์์ด์ ์ฌ์ ์์ผ๋ก ์ ๋ ฌ๋๋ค.
1
2
3
public int compareTo(Integer anotherInteger) {
return this.value - anotherInteger.value;
}
PriorityQueue ๋ ๊ธฐ๋ณธ์ ์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
1
2
3
4
5
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.poll(); // ์ฐ์ ์์ ํ ์์ ๋ค์ด์๋ ๊ฐ ์ค ์ ์ผ ์์ ๊ฐ ๋ฐํ.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.poll(); // ์ฐ์ ์์ ํ ์์ ๋ค์ด์๋ ๊ฐ ์ค ์ ์ผ ํฐ ๊ฐ ๋ฐํ.
์ฝ๋์ ๊ฐ์ด ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ๊ด๋ฆฌํ๊ธฐ ์ํด ์ต๋ํ๊ณผ ์ต์ํ์ ๋ง๋ค์ด ์คฌ๋ค. ๊ฐ์ ์ ์ฅ์์ ์์ชฝ์ ์ ์ฅ ํ, ๊ฐ์ ๋บ๋ ์ต์๊ฐ์ด๋ฉด ์ต์ํ์์ ๋นผ์ฃผ๊ณ ์ต๋๊ฐ์ด๋ฉด ์ต๋ํ์์ ๋นผ์ฃผ๋ฉด ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ์ ๋ฃ์๋ ์์ชฝ์ ๊ฐ์ด ๋ฃ์๊ธฐ ๋๋ฌธ์ ํ์ชฝ ํ์์ ๋น ์ง ๊ฐ์ ๋ค๋ฅธ์ชฝ ํ์์๋ ๋นผ์ค์ผ ์๋ก ๋๊ธฐํ๊ฐ ๋๋ค.
1
2
3
4
5
// ์ต๋๊ฐ์ ์ ๊ฑฐ ํ ์ต์ํ์์ ํด๋น ๊ฐ ์ ๊ฑฐ
minHeap.remove(maxHeap.poll());
// ์ต์๊ฐ์ ์ ๊ฑฐ ํ ์ต๋ํ์์ ํด๋น ๊ฐ ์ ๊ฑฐ
maxHeap.remove(minHeap.poll());
๋ฌธ์ ์
PriorityQueue์ remove ์ฐ์ฐ ์๊ฐ ๋ณต์ก๋
ํด๋น ์ฝ๋๋ remove()
๋ก ์ญ์ ํ๋ ๋ถ๋ถ์ด ๋ฌธ์ ์ธ๋ฐ, PriorityQueue
๊ฐ ํ์ ๊ตฌ์กฐ(์์ ์ด์งํธ๋ฆฌ)๋ฅผ ๊ฐ์ง๊ณ ์๋ ๊ฒ๊ณผ ๋ณ๊ฐ๋ก ์ญ์ ํ ์์๋ฅผ ํ์ํด์ผ ํ๊ธฐ ๋๋ฌธ์ ์ ์ฒด๋ฅผ ์ํํด์ผ ํ๋ค.
ํ์ ๋ชฉ์ ์ธ ์ต๋ / ์ต์ ๊ฐ์ ๋ฆฌํดํ๋ poll()
์ ์ฌ์ฉํ๋ ๊ฒ์์ ๋๋๋ ๊ฒ์ด ์๋๋ผ, for ๋ฌธ ์์์ remove()
๋ฅผ ํธ์ถํ๊ณ ์๋ค.
operations ๋ฐฐ์ด์์ โIโ ์ปค๋งจ๋๊ฐ ๋ง์์ง ์๋ก(ํ์ ๋ฃ๋ ์์
์ด ์ฆ๊ฐํ ์๋ก) remove ์ ํ์ํด์ผ ํ๋ ์๋ ๋์ด๋๋ค.
PriorityQueue ๊ฐ์
์ฒ์ ์์ฑํ ์ฝ๋์์ ๋ฌธ์ ๋๋ remove()
๊ณผ์ ์ ๊ฒฐ๊ตญ ์ฐพ๊ณ ์ ํ๋ ๊ฐ์ด ํธ๋ฆฌ์ ์ด๋์ ์๋์ง ๋ชจ๋ฅธ๊ธฐ ๋๋ฌธ์๋ฐ์ํ๋ค.
์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ต๋ํ/์ต์ํ์ ๊ฐ์ ๋ฃ์๋ ๊ฐ๊ณผ ๋๋ถ์ด ๊ณ ์ ์ธ๋ฑ์ค ๋ฒํธ๋ฅผ ๊ฐ์ด ์ ์ฅํ๊ธฐ ์ํด Node
ํด๋์ค๋ฅผ ๋ง๋ค์ด์ ์ ์ฅํ๋ค.
์ด๋ ๊ธฐ์กด์ int ๋ฅผ ์ ์ฅํ ๋๋ Integer ํด๋์ค์ Comparator ๊ฐ ์ด๋ฏธ ๊ตฌํ๋์ด ์์ด ๊ทธ๋๋ก ์ ์ฅํด๋ ์ ๋ ฌ์ด ๋์์ง๋ง, ์๋ก ๋ง๋ Node
ํด๋์ค๋ ์ด๋ค ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ ์ง ์ ์๋ฅผ ํด์ค์ผ ํ๋ค.
PriorityQueue
์ ์ฝ์
๋ ๋ ์ ๋ ฌ์ value ๋ฅผ ๊ธฐ์ค์ผ๋ก ํ๋๋ก compareTo
๋ฅผ ์ฌ์ ์ ํด์ค๋ค.
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
import java.util.*;
class Node implements Comparable<Node> {
int value;
int index;
Node(int value, int index) {
this.value = value;
this.index = index;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.value, o.value);
}
}
class Solution {
public int[] solution(String[] operations) {
PriorityQueue<Node> minHeap = new PriorityQueue<>();
PriorityQueue<Node> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
// minHeap ๊ณผ maxHeap ๋ชจ๋ ์ด ๋ฐฐ์ด์ ํตํด ์ญ์ ์ฌ๋ถ๋ฅผ ๊ด๋ฆฌํ๋ค.
boolean[] visited = new boolean[operations.length];
for (int i = 0, len = operations.length; i < len; i++) {
String command = operations[i];
if (command.contains("I")) {
int num = Integer.parseInt(command.split(" ")[1]);
Node node = new Node(num, i);
maxHeap.add(node);
minHeap.add(node);
visited[i] = true; // ์ฝ์
์ ํด๋น ์ธ๋ฑ์ค๋ฅผ ๋งํน ํ๋ค.
} else if (command.equals("D 1")) {
// ์ต๋๊ฐ ์ญ์
while (!maxHeap.isEmpty() && !visited[maxHeap.peek().index]) {
maxHeap.poll();
}
if (!maxHeap.isEmpty()) {
visited[maxHeap.poll().index] = false;
}
} else {
// ์ต์๊ฐ ์ญ์
while (!minHeap.isEmpty() && !visited[minHeap.peek().index]) {
minHeap.poll();
}
if (!minHeap.isEmpty()) {
visited[minHeap.poll().index] = false;
}
}
}
// ์ต์ข
์ถ๋ ฅ ์ ์ ํจํ์ง ์์ ๊ฐ ์ ๊ฑฐ
while (!minHeap.isEmpty() && !visited[minHeap.peek().index]) {
minHeap.poll();
}
while (!maxHeap.isEmpty() && !visited[maxHeap.peek().index]) {
maxHeap.poll();
}
int[] result = new int[2];
if (minHeap.isEmpty() || maxHeap.isEmpty()) {
result[0] = 0;
result[1] = 0;
} else {
result[0] = maxHeap.peek().value;
result[1] = minHeap.peek().value;
}
return result;
}
}
์ต๋๊ฐ์ ์ญ์ ํ๋ ๊ณผ์ ์ ์ดํด๋ณด๋ฉด
1
2
3
4
5
6
7
8
// ์ต์ํ/์ต๋ํ ๋๊ธฐํ ์ฝ๋
while (!maxHeap.isEmpty() && !visited[maxHeap.peek().index]) {
maxHeap.poll();
}
// maxHeap ์์ ๊ฐ์ ์ง์ฐ๊ณ visited ์ ์ง์ ๋ค๋ ๊ฒ์ ํ์ํ๋ค.
if (!maxHeap.isEmpty()) {
visited[maxHeap.poll().index] = false;
}
while ๋ฌธ์์ ์ต๋๊ฐ์ ์ธ๋ฑ์ค์ ํด๋นํ๋ visited ํญ๋ชฉ์ ๊ฐ์ด false ์ธ์ง ๊ฒ์ฌํ๊ณ ์๋ค.
์ด๋ I
์ปค๋งจ๋์ ์ํด ๊ฐ์ ๋ฃ๋ ๋ก์ง์์ ์ต๋ํ๊ณผ ์ต์ํ ๋ชจ๋์ ๊ฐ์ ๋ฃ๋๋ฐ, ๋ง์ฝ ๊ฐ์ ์ ๊ฑฐํ๋ ๊ณผ์ ์์ ์ต์ํ์ด๋ ์ต๋ํ ๋ ์ค ํ๋์์๋ง ๊ฐ์ด ์ ๊ฑฐ๋๋ ๊ฒฝ์ฐ์๋ ๋ ํ์ด ๋๊ธฐํ๋์ง ์๋๋ค.
์ด๋ฅผ ๋ฐฉ์งํ๊ธฐ ์ํ ์ฝ๋๊ฐ while ๋ฌธ์ด๋ค.
์๋ฅผ๋ค์ด, maxHeap
์ {100, 2}
๋ผ๋ Node ๊ฐ ๋ค์ด ์๋ค. ๊ทธ๋ฆฌ๊ณ ์ด ๋
ธ๋์ ์ธ๋ฑ์ค์ ํด๋นํ๋ visited[2]
๊ฐ์ด false ๋ผ๊ณ ํด๋ณด์.
visited
์ ๊ฐ์ด false ๋ผ๋ ์๋ฏธ๋ ์ด๋ฏธ minHeap
์์ ์ต์๊ฐ์ ์ ๊ฑฐํ๋ ๊ณผ์ ์์ visited
๋ฐฐ์ด์ ์ธ๋ฑ์ค ๊ฐ์ false ๋ก ๋ฐ๊พธ์๋ค๋ ์๋ฏธ์ด๋ค.
๊ทธ๋ฐ๋ฐ ์ด ์ํ๋ก 37๋ฒ ๋ผ์ธ์ด ํธ์ถ๋์๋ค๋ฉด ๋
ผ๋ฆฌ์์ ์ค๋ฅ๊ฐ ๋ฐ์ํ ์
์ด๋ค. ํ ๊ฐ์ ๋๊ธฐํ๊ฐ ์ ๋๋ก ์ด๋ฃจ์ด์ง์ง ์์๋ค๋ ๋ป์ด๋ค.
์ด๋ฐ ์ ํจํ์ง ์์ ๊ฐ์ ์ ๊ฑฐํ๋ ๋ก์ง์ด๋ผ๊ณ ๋ณด๋ฉด ๋๋ค.
๊ทธ๋ฆฌ๊ณ 54๋ฒ ๋ผ์ธ์์ ์ต์ข
์ ์ผ๋ก ๊ฐ๊ฐ์ ํ์ ๋ค์ด์๋ ๊ฐ์ ๊ฒ์ฆํ๋ค. ์ด๋ฏธ ์ญ์ ๋ ๊ฐ์ด๋ผ๋ฉด (visited[maxHeap.peek().index]
๊ฐ false), ์ด ์์๋ฅผ poll()์ ํตํด ์ ๊ฑฐํ๋ค.
TreeMap ์ ์ฌ์ฉํ ํ์ด
(์ถ์ฒ: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)
PriorityQueue
์ ์์ชฝ์์ ๊ฐ์ ๋บ ์๊ฐ ์์ด, ์ต๋ํ๊ณผ ์ต์ํ์ ๋๊ฐ ๋ง๋ค๊ณ ์๋ก ๋๊ธฐํ ์ํค๋ ์์
์ด ํ์ํ๋ค. ์ด ๋๊ธฐํ ์ํค๋ ์ฝ๋๋ฅผ ์ง์ ์ง๋ ๊ฒ์ด ํต์ฌ์ด๊ณ , ๊ทธ ๋ฐฉ๋ฒ์ ์๊ฐํ๋ ๊ฒ๋ ์ฝ์ง ์๋ค. ๊ทธ๋ฆฌ๊ณ ํน์ ๊ฐ์ ํ์ํ๋๋ฐ O(n) ์ ์๊ฐ๋ณต์ก๋๊ฐ ๊ฑธ๋ฆฐ๋ค.
๊ทธ์ ๋ฐํด TreeMap
์ ์ด์งํ์ํธ๋ฆฌ์ ๊ตฌ์กฐ๋ฅผ ๊ฐ๊ณ ์์ด, ๊ฐ ์ฝ์
์ ๊ธฐ์กด ๋
ธ๋์ ๋น๊ตํด ๋ ํฐ ๊ฐ์ ์ค๋ฅธ์ชฝ์, ๋ ์์ ๊ฐ์ ์ผ์ชฝ์ ์ ์ฅํ๋ ๊ท์น์ด ์๋ค. ๊ฒฐ๊ตญ ์ด ๋ฌธ์ ๋ ์ต๋/์ต์๊ฐ์ด ๋ชจ๋ ํ์ํ ๋ฌธ์ ์ด๊ธฐ ๋๋ฌธ์ ์ฐ์ ์์ํ ๋ณด๋จ ํธ๋ฆฌ๋งต์ ์ฐ๋ ๊ฒ์ด ๊ตฌํ์ ๋ณต์ก๋๊ฐ ๋ฎ์ ๋ณด์ธ๋ค.
๋ ์์ธํ ์ดํด๋ณด์๋ฉด TreeMap
๋ ์ด์งํ์ํธ๋ฆฌ๋ฅผ ๊ฐ์ ํ Red-Black Tree
ํํ๋ฅผ ๊ฐ์ง๊ณ ์๋ค.
๊ธฐ์กด ์ด์งํ์ํธ๋ฆฌ์ ๋จ์ ์ ํธ๋ฆฌ์ ํธํฅ๋ ๊ฐ๋ง ๋ค์ด์ฌ ๊ฒฝ์ฐ ํ์ชฝ์ผ๋ก ๊ฐ์ด ์ ๋ฆฌ๊ฒ ๋๋ค.
๊ทธ๋ฌ๋ฉด ๊ฒฐ๊ตญ ํ์ํ๋ ์๊ฐ์ด ํธ๋ฆฌ์ ๊น์ด์ ๋น๋กํ๊ธฐ ๋๋ฌธ์ ์ต์
์ ๊ฒฝ์ฐ ํธ๋ฆฌ์ ์ต๋ ๊น์ด๊น์ง ํ์ํด์ผ ํ๋ค.
Red-Black Tree
๋ ๋ค์๊ณผ ๊ฐ์ ์์ฑ์ ๊ฐ๊ณ ์๋ค.
- ๋ชจ๋ ๋ ธ๋๋ ๋ ๋ ์๋๋ฉด ๋ธ๋์ด๋ค.
- ๋ฃจํธ ๋ ธ๋๋ ๋ธ๋์ด๋ค.
- ๋ชจ๋ NIL(leaf) ๋ ธ๋๋ ๋ธ๋์ด๋ค.
- ๋ ๋ ๋
ธ๋๋ ๋ ๋ ๋
ธ๋๋ฅผ ์์์ผ๋ก ๊ฐ์ง ์ ์๋ค. ๋ฐ๋ผ์โฆ
- ๋ชจ๋ ๋ ๋ ๋ ธ๋์ ๋ถ๋ชจ๋ ๋ธ๋์ด๋ค.
- ๋ ๋ ๋ ธ๋๋ ์ฐ์์ผ๋ก ์กด์ฌ(Double red)ํ ์ ์๋ค.
- ์์์ ํ ๋ ธ๋์์ NIL ๋ ธ๋๊น์ง ๋๋ฌํ๋ ๋ชจ๋ ๊ฒฝ๋ก์๋ ํญ์ ๊ฐ์ ์์ ๋ธ๋ ๋ ธ๋๊ฐ ์๋ค.
ํธ๋ฆฌ์ ๊ฐ์ ์ฝ์ ํ ํญ์ ์ ํน์ฑ์ ๋ฐ๋ผ์ ํธ๋ฆฌ์ ๊ตฌ์กฐ๋ฅผ ์ฌ์กฐ์ ํ๋ค๋ณด๋ฉด ๋ชจ์์ด ๊ท ํ์ ์ด๋ฃฌ๋ค๋ ๊ฒ์ด๋ค. ์๋ฅผ ๋ค์ด ํ์ฌ ํธ๋ฆฌ์ ๋ค์๊ณผ ๊ฐ์ด ๊ฐ์ด ๋ค์ด๊ฐ ์๋ค๊ณ ํด๋ณด์.
์ฌ๊ธฐ์ ์ด์งํ์ํธ๋ฆฌ์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ฉด์, ๋ ๋-๋ธ๋ ํธ๋ฆฌ์ ์์ฑ์ ๋ง์กฑ์ํค๋ ค๋ฉด ์ฝ์ ๋๋ ๋ ธ๋๋ ๋นจ๊ฐ์์ผ๋ก ์์ํด์ผ ํ๋ค.
๋ ๋-๋ธ๋ ํธ๋ฆฌ์ ์์ฑ์ ์ ์งํ๊ธฐ ์ํด ์ค๋ฅธ์ชฝ์ผ๋ก ํ์ ํ ์์ ๋ค์ ๋ณ๊ฒฝํด์ฃผ๋ฉด
์ต์ข ์ ์ผ๋ก ๋ค์๊ณผ ๊ฐ์ ๋ชจ์ต์ด ๋๋ค.
(์ถ์ฒ : https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)
๋ ๋-๋ธ๋ ํธ๋ฆฌ๋ ํธ๋ฆฌ์ ๊น์ด๋ฅผ ํญ์ ์ผ์ ํ๊ฒ ์ ์งํ๊ธฐ ๋๋ฌธ์ ์๊ฐ๋ณต์ก๋๋ worst case ์ average case ๋ชจ๋ O(log n) ์ด ๊ฑธ๋ฆฐ๋ค.
๋ ๋-๋ธ๋ ํธ๋ฆฌ ์๋ฎฌ๋ ์ด์ ์ ์ฌ๊ธฐ์ ๊ฐ๋ฅํ๋ค.
์ฝ๋
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
class Solution {
public int[] solution(String[] operations) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (String command : operations) {
if (command.contains("I")) {
String num = command.split(" ")[1];
map.put(Integer.valueOf(num), map.getOrDefault(Integer.valueOf(num), 0) + 1);
} else if (command.equals("D 1")) {
if (map.isEmpty()) {
continue;
}
Integer max = map.lastKey();
if (map.get(max) == 1) {
map.remove(max);
} else {
map.put(max, map.get(max) - 1);
}
} else {
if (map.isEmpty()) {
continue;
}
Integer min = map.firstKey();
if (map.get(min) == 1) {
map.remove(min);
} else {
map.put(min, map.get(min) - 1);
}
}
}
int[] result = new int[2];
if (map.isEmpty()) {
result[0] = 0;
result[1] = 0;
} else {
result[0] = map.lastKey();
result[1] = map.firstKey();
}
return result;
}
}
์ด์งํ์ ํธ๋ฆฌ์ ์ผ์ข ์ด๊ธฐ ๋๋ฌธ์ ๊ฐ์ฅ ์ผ์ชฝ๊ฐ์ด ์ ์ผ ์๊ณ , ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ๊ฐ์ด ์ ์ผ ํฌ๋ค. ๋ฐ๋ผ์ ๋ฃจํธ ๋ ธ๋์์๋ถํฐ ๊ฐ์ฅ ์ผ์ชฝ ๊ฐ์ ๋ฐํํ๋ ๋ฉ์๋์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ๊ฐ์ ๋ฐํํ๋ ๋ฉ์๋๋ฅผ ์ ๊ณตํ๊ณ ์๋ค.
๋๊ธ๋จ๊ธฐ๊ธฐ