230525 Today I Learned

아침에 코테 문제를 풀었는데 테스트 통과는 되었지만, 시간복잡도 측면에서 뭔가 아쉬워서 다른 방법을 찾아보았다.

이중 우선순위큐 문제

프로그래머스 lv.3 문제인 이중우선순위큐를 풀었다.
최대값과 최소값을 한번에 컨트롤 하는 문제여서 우선순위큐를 min과 max 두개를 사용해서 풀어 통과를 했지만 시간복잡도가 마음에 들지 않았다.

• 풀이과정

public class T_이중우선순위큐 {
  public int[] solution(String[] operations) {
    PriorityQueue<Integer> pqMax = new PriorityQueue<>(Comparator.reverseOrder());
    PriorityQueue<Integer> pqMin = new PriorityQueue<>();

    for (String operation : operations) {
      if (operation.charAt(0) == 'I'){
        String numString = operation.substring(2);
        Integer num = Integer.parseInt(numString);
        pqMax.offer(num);
        pqMin.offer(num);
      } else if (operation.equals("D 1")){
        if (pqMax.isEmpty()) continue;
        Integer maxNum = pqMax.poll();
        pqMin.remove(maxNum);
      } else if (operation.equals("D -1")){
        if (pqMin.isEmpty()) continue;
        Integer minNum = pqMin.poll();
        pqMax.remove(minNum);
      }
    }
    Integer max = pqMax.peek();
    Integer min = pqMin.peek();

    if (max == null) max = 0;
    if (min == null) min = 0;

    int[] answer = {max, min};

    return answer;
  }

• 최대힙과 최소힙으로 우선순위 큐를 두개 구현하고 삽입은 같이 삽입하되, 최대 최소값 연산은 각각의 큐에서 진행하고 remove로 그 값을 다른 큐에서 제거하게 했다.

• 그러나 위와 같은 풀이 방법에서는 힙에서 비효율적인 연산인 remove()를 수행해야 했다. remove()는 힙 내부를 순회해 값을 찾기 때문에 O(N)의 시간복잡도를 가지고, 이때문에 해당 코드 전체 시간복잡도가 최악의 경우 O(N^2)이 되어버린다. 프로그래머스에서는 이 답안을 통과시키긴 했지만 시간복잡도를 더 개선할 수 있는 풀이 방향이 있을 것 같아서 알아보았다.

• 힙이 아니라 이진탐색트리를 기반으로 문제를 풀면 remove 연산을 할 때 O(N)이 아니라 O(log N)이 소요되니 더 낮은 시간복잡도로 문제를 해결할 수 있을 것 같았다.

• 그래서 TreeSet으로 문제를 풀어보니 Set은 중복 값을 저장하지 못해 테스트케이스에 만약 중복 값이 있으면 처리되지 못하는 문제가 있었다. 그래서 TreeMap으로 문제를 풀어보고자 했다.

TreeMap

Java 17 TreeMap 공식문서

Red-Black 트리를 기반으로 한 Map 컬렉션
정렬된 상태로 Map을 유지하거나 정렬된 데이터를 조회, 범위 검색시 유용하다.

• TreeSet과 달리 key-value 타입(Entry)으로 데이터를 저장한다.

• 객체를 저장하면 자동으로 정렬을 한다. 그래서 추가, 삭제시 map으로서의 성능은 hashmap보다 떨어진다.

• 키는 자동으로 오름차순으로 정렬되고, 숫자는 값으로, 문자열은 유니코드가 기준이다.

• 기본적으로 부모의 키 값과 비교해서 값이 낮으면 왼쪽, 높으면 오른쪽 자식노드에 저장된다.

• 메서드는 위의 공식문서 링크 참고.

관련자료구조

• Map : 자바 컬렉션 프레임워크 중 하나로 key-value로 데이터를 저장하는 자료구조

• 이진탐색트리(BST, binary search tree)
  부모의 왼쪽에는 부모 노드보다 작은 값, 오른쪽에는 큰 값을 저장하는 이진트리.
  왼쪽자식 -> 부모 -> 오른쪽 자식 순으로 읽으면 오름차순으로 정렬된 결과를 볼 수 있다.
  범위 검색과 정렬에 유리하고 중복값을 저장하지 못한다.
  모든 노드는 최대 2개의 자식노드를 가질 수 있다.

• Red-Black Tree : 이진탐색트리의 속성을 유지하면서 문제점을 보완한 자료구조.
  이상적인 상황이나 최악이나 탐색/삽입/삭제에 모두 시간복잡도가 O(log N)이다.
  이진탐색트리는 일반적으로 트리의 높이만큼 시간복잡도가 소요되는데, 기존 이진탐색트리는 한쪽으로 트리가 치우쳐져 비효율적인 성능을 낼 수 있다.
  레드블랙트리는 트리의 높이를 최소화해 효율적인 연산을 보장한다.
  트리의 노드는 레드와 블랙 두 가지 색깔을 갖는다.
  루트 노드는 항상 블랙. 레드 노드는 연속해서 올 수 없다.
  자식이 하나도 없는 리프노드에는 NIL 블랙 노드를 붙인다.

• TreeSet : TreeMap과 마찬가지로 Red-Black트리로 구현되어 삽입, 삭제, 탐색에 O(log N)이 소요된다. 중복을 허용하지 않고 정렬된 순서로 저장한다.

힙과 이진탐색트리(레드블랙트리)의 비교

• 두 자료구조 다 이진트리 기반이다.

• 힙은 최대값과 최소값에 대한 접근이 O(1)로 매우 빨라 최대, 최소값을 얻기 위해서 쓰이며, 이진탐색트리는 탐색이 필요할 때 사용된다.

• 이진탐색트리는 왼쪽자식 < 부모 < 오른쪽 자식 으로 항상 정렬된 순서를 유지한다.
  최대(최소)힙은 부모노드의 값이 항상 자식노드보다 크거나 같고(작거나 같고) 정렬된 순서는 유지하지 않는다.

• 둘 다 삽입과 삭제는 O(log n)의 시간복잡도를 갖는다.
  (이진탐색트리는 최악의 경우 트리가 치우쳐져있을 때 O(n)이 소요되지만 이를 보완한 레드블랙트리의 경우 어떠한 경우에서도 O(log N)이 소요된다.)

• 이진탐색트리는 포인터 기반의 구현이 일반적이고, 힙은 배열기반이 일반적이다.

TreeMap으로 문제 풀이

TreeMap<Integer, Integer> map = new TreeMap<>();

for (String operation : operations) {
//      StringTokenizer로 공백을 기준으로 문자열을 분리
  StringTokenizer st = new StringTokenizer(operation, " ");
  String ch = st.nextToken();
  Integer num = Integer.parseInt(st.nextToken());

  if (ch.equals("I")){
//        map의 key에 숫자를 넣고, value에 map에 있는 해당 숫자의 갯수를 넣는다. 
//        중복숫자가 없으면 getOrDefault는 0을 반환한다.
    int count = map.getOrDefault(num, 0);
    map.put(num, count+1);
//        D로 시작하고, map에 값이 있을때 아래 로직 실행
  }else if (ch.equals("D") && !map.isEmpty()) {
//        최대값은 map.lastKey(), 최소값은 map.firstKey()로 뽑아낸다.
    int key = num == 1 ? map.lastKey() : map.firstKey();
    int count = map.get(key);
//        해당 키가 여러개 있으면 카운트를 1차감하고, 없으면 키를 삭제한다.
    if (count == 1) {
      map.remove(key);
    } else {
      map.put(key, count -1);
    }
  }
}
if (map.isEmpty()){
  return new int[]{0,0};
} else {
  return new int[]{map.lastKey(), map.firstKey()};
}

• charAt()과 subString()으로 문자열을 분리했던걸 StringTokenizer를 써서 풀어봤다. 공백을 기준으로 분리를 하고 nextToken()을 쓰면 순서대로 문자열이 나온다.

• key에는 숫자를, value에는 해당 숫자의 갯수를 넣어 중복 값을 처리했다.

• 단순히 최소값, 최대값을 뽑아낼 때는 힙을 썼을 때 보다 O(1)에서 O(log N)으로 시간복잡도가 늘어났다.

• 하지만 원래 코드에서 삭제에 O(N)이 걸리던걸 O(log N)으로 줄여
  전체 코드에서 시간복잡도가 O(N^2)에서 O(N log N)으로 줄었다.