[BOJ] 우선선위 큐 (Priority Queue) & TreeMap

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 요소가 특정 우선순위에 따라 정렬되는 큐 인터페이스의 구현체로, 항상 우선순위가 높은 요소를 먼저 꺼낼 수 있다. 기본적으로 우선순위 큐는 힙(Heap) 자료구조를 기반으로 동작한다.

 

힙이란?

 

이진 트리 기반의 자료구조로, 특정 규칙에 따라 부모 노드와 자식 노드 간의 관계를 유지하며 최댓값 또는 최솟값을 찾아내는 연산이 빠르다. 힙은 최대 힙, 최소힙 두 가지 유형으로 구분된다.

 

Java에서는 힙을 PriorityQueue 클래스를 사용해 구현할 수 있다.

주로 오름차순, 내림차순 정렬 방식을 이용하여 큐를 정의한다.

오름차순

 PriorityQueue<Integer> pq = new PriorityQueue<>();

 

내림차순

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
	return o2 - o1;
});

 

 

우선순위 큐의 메소드는 Queue 메소드와 비슷하다.

 

1. 삽입

pq.add(value)

 

2. 삭제

큐 요소 삭제 방식으로는 두 가지가 있다.

기본적으로 둘 다 우선순위가 가장 높은 요소가 제거되며, Exception 발생 여부의 차이이다.

pq.remove()

 

큐가 비어있는 경우 NoSuchElementException이 발생한다.

pq.poll()

 

큐가 비어있는 경우 null을 반환한다.

pq.remove(value)

값을 알고 있을 경우, 삭제할 값을 지정하여 제거할 수도 있다.

 

3. 맨 앞 요소 확인

pq.peek()

 

4. 초기화

pq.clear()

 

5. 크기

pq.size();

 

6. 공백 여부

pq.isEmpty()

 

 

[ 프로그래머스 ] 이중우선순위큐

가장 풀어보기 적당한 문제는 프로그래머스의 이중우선순위큐 이다.

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

우선순위 큐 풀이

import java.util.*;

class Solution {
    static int n;
    public int[] solution(String[] operations) {
        int[] answer = {};
        n = operations.length;
        
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>((o1, o2) -> {
            return o2 - o1;
        });
        
        for(int i = 0; i < n; i++){
            String[] str = operations[i].split(" ");
            int num = Integer.parseInt(str[1]);
            
            if (str[0].equals("I")) {
                min.add(num);
                max.add(num);
            } else if(!min.isEmpty()) {
                int m = 0;
                if(num == 1) m = max.peek();
                else m = min.peek();
                
                max.remove(m);
                min.remove(m);
            }
        }
        
        if(min.isEmpty()) {
            answer = new int[]{0, 0};
        } else if(min.size() == 1) {
            int num = min.peek();
            answer = new int[]{num, num};
        } else {
            answer = new int[]{max.peek(), min.peek()};
        }
        
        return answer;
    }
}

 

 

[ BOJ 7662 ] 이중 우선순위 큐

https://www.acmicpc.net/problem/7662

 

백준에서도 비슷한 문제가 있어 위의 프로그래머스 풀이대로 삭제 명령마다 remove()를 호출하였는데, 시간 초과가 발생하였다. remove()의 시간 복잡도가 O(n)인데, k가 최대 1,000,000까지 입력될 경우 O(n)이 반복된 것이 원인이였고, TreeMap을 사용하였다.

 

 

TreeMap이란?

 

이진트리를 기반으로 한 Map 컬렉션이다. TreeMap에 객체를 저장하면 키를 정렬된 상태로 유지한다. 기본적으로 오름차순으로 정렬하며, 사용자 정의 Comparator를 통해 정렬할 수 있다. HashMap 보다는 삽입, 검색 성능이 떨어지지만, 정렬된 데이터가 필요할 때 유용하다.

 

* 정렬기준 : 숫자 > 알파벳 대문자 > 알파벳 소문자 > 한글

 

HashMap과 TreeMap 차이점

특징	HashMap	TreeMap
저장 구조	해시 테이블	레드-블랙 트리
정렬 여부	없음	키에 따라 정렬
삽입/검색 시간 복잡도	O(1)	O(log N)
적용 예	빠른 검색과 삽입이 필요할 때	정렬된 데이터가 필요할 때

 

 

레드-블랙 트리란?

 

ㄹ

이진 탐색 트리의 문제점을 보완한 트리이다. 일반적으로 이진 탐색 트리는 트리의 높이만큼 O(logN) 시간 복잡도를 지닌다. 값이 분산되어 있다면 문제가 없지만, 한쪽으로 편향되어있을 경우 최악 시간 복잡도는 O(N)이다.

 

 

새로운 노드를 삽입하면 기본적으로 빨강으로 설정된다. 삽입 후 트리의 규칙을 위반하여 Double Red가 발생한 경우, 두 가지 전략을 사용할 수 있다.

1. Restructuring
   왼쪽 회전 또는 오른쪽 회전을 사용하여 트리의 구조를 재배치한다.
   
   
2. Recoloring
   규칙을 위반한 경우 노드 색상을 변경한다.

마찬가지로 삭제 후 Double Red가 발생하면, 두 가지 전략을 통해 복원한다.

 

예제 입력 1

2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333

 

예제 출력 1

EMPTY
333 -45

 

TreeMap 풀이

import java.io.*;
import java.util.*;

public class Main {
  static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  public static void main(String [] args) throws IOException{
    int t = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();

    for(int i = 0; i < t; i++){
      int k = Integer.parseInt(br.readLine());
      TreeMap<Integer, Integer> map = new TreeMap<>();
      
      while (k --> 0) {
        String[] str = br.readLine().split(" ");
        int num = Integer.parseInt(str[1]);

        if(str[0].equals("I")){
          map.put(num, map.getOrDefault(num, 0) + 1);
        } else {
          if (map.isEmpty()) continue; 
          else {
            int n = (num == 1) ? map.lastKey() : map.firstKey();
            if (map.put(n, map.get(n) - 1) == 1) {
              map.remove(n);
            }
          }
        }
      }

      if(map.isEmpty()){
        sb.append("EMPTY").append("\n");
      } else {
        sb.append(map.lastKey()).append(' ').append(map.firstKey()).append("\n");
      }
    }
    
    System.out.println(sb.toString());
  }
};