[TIL] 99클럽 코테 스터디 19일차 TIL 우선 순위 큐 (Priority Queue) + 백준 1374 강의실

 

문제 풀이

 

문제 탐색하기

문제를 읽어보면 강의실을 배정하는 규칙을 알 수 있습니다. 강의실에 배정된 강의가 끝나는 시간이 다음 강의가 시작하는 시작시간보다 클 경우 새 강의실에서 강의를 시작해야 한다는 것과 시작시간보다 작은 강의실이 있다면 다음 강의를 진행할 수 있다는 것입니다.

 

강의 시작시간과 끝나는 시간은 2차원 배열을 활용하여 오름차순 정렬 후 탐색에 사용합니다.

 

여기서 매 탐색마다 제일 빠르게 끝나는 강의실을 찾는 것이 중요합니다. 이 부분을 우선순위 큐를 활용하여 문제를 풀 수 있습니다.

 

우선 순위 큐(Priority Queue)란?

큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 FIFO(First In First Out)의 구조 즉 먼저 들어온 데이터가 먼저 나가는 구조를 뜻합니다. Priority Queue는 먼저 들어온 순서대로 데이터가 나가는 것이 아니라 우선순위를 먼저 결정하고 우선순위가 높은 요소가 먼저 나가는 자료구조입니다. 

우선 순위 큐는 힙을 이용하여 구현하는 것이 일반적입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대 힙 또는 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 이동하는 방식으로 진행됩니다. 

 

Priority Queue의 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야함)
2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음   
3. 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)
4. 우선순위를 중요시해야 하는 상황에서 사용

Priority Queue 사용하기

기본적인 우선 순위 큐를 사용하는 방법은 다음과 같습니다.

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (오름차순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (내림차순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (오름차순 : 사전 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (내림차순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

비교 가능한 기준이 있는 원소라면 위의 기본적인 선언으로 우선 순위 큐를 사용할 수 있습니다. 

Priority Queue 안에 담길 객체를 Custom Class를 사용하고 싶다면 Comparable Interface를 implements 하는 클래스를 생성 후, compareTo method를 활용하여 비교 가능한 기준을 부여해 주면 됩니다.

 

큐의 기본적인 메소드는 아래와 같습니다.

// 큐에 값 추가
priorityQueue.add(object);

// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.poll();

// 첫번째 값 제거 비어있다면 예외 발생
priorityQueue.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueue.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueue.element();

// 초기화
priorityQueue.clear();

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int[][] classTime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        classTime = new int[N][3];

        StringTokenizer st;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            classTime[i][0] = Integer.parseInt(st.nextToken());
            classTime[i][1] = Integer.parseInt(st.nextToken());
            classTime[i][2] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(classTime, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] != o2[1] ? o1[1] - o2[1] : o1[2] - o2[2];
            }
        });

        PriorityQueue<Integer> classRoom = new PriorityQueue<>();
        classRoom.add(0);

        for(int i=0; i<classTime.length; i++){
            int classEndTime = classRoom.peek();

            if(!(classEndTime > classTime[i][1])){
                classRoom.poll();
            }

            classRoom.add(classTime[i][2]);
        }

        System.out.println(classRoom.size());
    }
}

 

오늘의 회고

우선 순위 큐로 문제를 풀어볼 수 있는 좋은 문제였던 것 같습니다. 이렇게 문제에 활용할 수 있는 자료구조에 대해서 알아두는 것이 중요하다느 생각을 하게 되었습니다.