Publish:

ํƒœ๊ทธ: , , , , ,

์นดํ…Œ๊ณ ๋ฆฌ:

img_3.png

๋ฌธ์ œ

๋ฌธ์ œ ๋งํฌ

img_3.png

ํ’€์ด

์ฒซ๋ฒˆ์งธ ํ’€์ด

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;
}

img_5.png 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 ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์†์„ฑ์„ ๊ฐ–๊ณ  ์žˆ๋‹ค.

  1. ๋ชจ๋“  ๋…ธ๋“œ๋Š” ๋ ˆ๋“œ ์•„๋‹ˆ๋ฉด ๋ธ”๋ž™์ด๋‹ค.
  2. ๋ฃจํŠธ ๋…ธ๋“œ๋Š” ๋ธ”๋ž™์ด๋‹ค.
  3. ๋ชจ๋“  NIL(leaf) ๋…ธ๋“œ๋Š” ๋ธ”๋ž™์ด๋‹ค.
  4. ๋ ˆ๋“œ ๋…ธ๋“œ๋Š” ๋ ˆ๋“œ ๋…ธ๋“œ๋ฅผ ์ž์‹์œผ๋กœ ๊ฐ€์งˆ ์ˆ˜ ์—†๋‹ค. ๋”ฐ๋ผ์„œโ€ฆ
    • ๋ชจ๋“  ๋ ˆ๋“œ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ๋Š” ๋ธ”๋ž™์ด๋‹ค.
    • ๋ ˆ๋“œ ๋…ธ๋“œ๋Š” ์—ฐ์†์œผ๋กœ ์กด์žฌ(Double red)ํ•  ์ˆ˜ ์—†๋‹ค.
  5. ์ž„์˜์˜ ํ•œ ๋…ธ๋“œ์—์„œ NIL ๋…ธ๋“œ๊นŒ์ง€ ๋„๋‹ฌํ•˜๋Š” ๋ชจ๋“  ๊ฒฝ๋กœ์—๋Š” ํ•ญ์ƒ ๊ฐ™์€ ์ˆ˜์˜ ๋ธ”๋ž™ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค.

ํŠธ๋ฆฌ์— ๊ฐ’์„ ์‚ฝ์ž… ํ›„ ํ•ญ์ƒ ์ € ํŠน์„ฑ์— ๋”ฐ๋ผ์„œ ํŠธ๋ฆฌ์˜ ๊ตฌ์กฐ๋ฅผ ์žฌ์กฐ์ • ํ•˜๋‹ค๋ณด๋ฉด ๋ชจ์–‘์ด ๊ท ํ˜•์„ ์ด๋ฃฌ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ํ˜„์žฌ ํŠธ๋ฆฌ์— ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ฐ’์ด ๋“ค์–ด๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•ด๋ณด์ž.

img_5.png

์—ฌ๊ธฐ์— ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ์˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋ฉด์„œ, ๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ์˜ ์†์„ฑ์„ ๋งŒ์กฑ์‹œํ‚ค๋ ค๋ฉด ์‚ฝ์ž…๋˜๋Š” ๋…ธ๋“œ๋Š” ๋นจ๊ฐ„์ƒ‰์œผ๋กœ ์‹œ์ž‘ํ•ด์•ผ ํ•œ๋‹ค.

img_6.png

๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ์˜ ์†์„ฑ์„ ์œ ์ง€ํ•˜๊ธฐ ์œ„ํ•ด ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํšŒ์ „ ํ›„ ์ƒ‰์„ ๋‹ค์‹œ ๋ณ€๊ฒฝํ•ด์ฃผ๋ฉด

์ตœ์ข…์ ์œผ๋กœ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ชจ์Šต์ด ๋œ๋‹ค.

img_8.png

(์ถœ์ฒ˜ : 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;
    }
}

์ด์ง„ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์ผ์ข…์ด๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ€์žฅ ์™ผ์ชฝ๊ฐ’์ด ์ œ์ผ ์ž‘๊ณ , ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ๊ฐ’์ด ์ œ์ผ ํฌ๋‹ค. ๋”ฐ๋ผ์„œ ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ๋ถ€ํ„ฐ ๊ฐ€์žฅ ์™ผ์ชฝ ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ๋ฉ”์†Œ๋“œ์™€ ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ๋ฉ”์†Œ๋“œ๋ฅผ ์ œ๊ณตํ•˜๊ณ  ์žˆ๋‹ค. img_5.png

๋ฐฉ๋ฌธํ•ด ์ฃผ์…”์„œ ๊ฐ์‚ฌํ•ฉ๋‹ˆ๋‹ค! ๋Œ“๊ธ€,์ง€์ ,ํ”ผ๋“œ๋ฐฑ ์–ธ์ œ๋‚˜ ํ™˜์˜ํ•ฉ๋‹ˆ๋‹ค๐Ÿ˜Š

๋Œ“๊ธ€๋‚จ๊ธฐ๊ธฐ