[PS] 99클럽 코테 스터디 10일차 TIL (이중우선순위큐)

문제

문제 링크

풀이

첫번째 풀이

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 메소드에 의해 정렬된다. 숫자는 오름차순으로, 문자열은 사전순으로 정렬된다.

public int compareTo(Integer anotherInteger) {
    return this.value - anotherInteger.value;
}

PriorityQueue 는 기본적으로 오름차순 정렬

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.poll();     // 우선순위 큐 안에 들어있는 값 중 제일 작은 값 반환.

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.poll();     // 우선순위 큐 안에 들어있는 값 중 제일 큰 값 반환.

코드와 같이 최대값과 최소값을 관리하기 위해 최대힙과 최소힙을 만들어 줬다. 값을 저장시에 양쪽에 저장 후, 값을 뺄때 최소값이면 최소힙에서 빼주고 최대값이면 최대힙에서 빼주면 된다. 그리고 값을 넣을때 양쪽에 같이 넣었기 때문에 한쪽 힙에서 빠진 값은 다른쪽 힙에서도 빼줘야 서로 동기화가 된다.

// 최대값을 제거 후 최소힙에서 해당 값 제거
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 를 재정의 해준다.

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

최대값을 삭제하는 과정을 살펴보면

// 최소힙/최대힙 동기화 코드
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 노드까지 도달하는 모든 경로에는 항상 같은 수의 블랙 노드가 있다.

트리에 값을 삽입 후 항상 저 특성에 따라서 트리의 구조를 재조정 하다보면 모양이 균형을 이룬다는 것이다. 예를 들어 현재 트리에 다음과 같이 값이 들어가 있다고 해보자.

여기에 이진탐색트리의 조건을 만족하면서, 레드-블랙 트리의 속성을 만족시키려면 삽입되는 노드는 빨간색으로 시작해야 한다.

레드-블랙 트리의 속성을 유지하기 위해 오른쪽으로 회전 후 색을 다시 변경해주면

최종적으로 다음과 같은 모습이 된다.

(출처 : https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)

레드-블랙 트리는 트리의 깊이를 항상 일정하게 유지하기 때문에 시간복잡도는 worst case 와 average case 모두 O(log n) 이 걸린다.

레드-블랙 트리 시뮬레이션은 여기서 가능하다.

코드

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

이진탐색 트리의 일종이기 때문에 가장 왼쪽값이 제일 작고, 가장 오른쪽 값이 제일 크다. 따라서 루트 노드에서부터 가장 왼쪽 값을 반환하는 메소드와 가장 오른쪽 값을 반환하는 메소드를 제공하고 있다.