[백준]JAVA - 1931번: 회의실 배정

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

1931번: 회의실 배정

풀이

회의가 겹치지않도록 최대한 많은 회의를 배정하는 게 이 문제의 목표이다.

쉽게 말해서 이전 회의 종료 시간과 이후 회의 시작 시간이 겹치지 않으면 된다. 그리고 최대한 많은 회의를 하려면 종료 시간이 짧은 회의를 선택해야한다.

 

우선 문제를 쉽게 해결하기 위해서 종료 시간을 오름차순으로 정렬해야한다.

Arrays.sort(times, new Comparator<int[]>() {

    @Override
    public int compare(int[] o1, int[] o2) {
        // 종료 시간이 같다면 시작 시간이 빠른순으로 정렬
        if (o1[1] == o2[1]) return o1[0] - o2[0];
				
        return o1[1] - o2[1];
    }
});

오름차순으로 정렬하기 위해서는 Comparator 인터페이스를 활용해야한다. Comparator 인터페이스를 간단하게 설명하자면 compare 메서드를 통해서 두 개의 인자를 비교한 후에 정렬하는 것이다. 자바에서는 기본적으로 오름차순으로 정렬을 한다. 그렇다면 compare 메서드에서는 어떨까?

 

오름차순을 다르게 말하면 다음 값이 이전 값보다 크다는 뜻이다. 이렇게 생각하면 위의 코드를 이해하기 쉬울 것이다. 첫 번째 인자에서 두 번째 인자를 빼면 음수, 양수의 경우가 나온다. 

 

return o1[0] - o2[0] 에서 o1값을 5, o2 값을 3이라고 가정해보자. 5-3은 2로 양수가 될 것이다. 그렇다면 이전 값이 다음 값보다 크다는 결과가 나오기 때문에 두 개 인자의 위치를 변경하게 되는 것이다.

 

음수일 경우: 두 원소의 위치를 교환 안함

양수일 경우: 두 원소의 위치를 교환 함

 

다시 문제로 돌아와서 종료 시간이 똑같을 때 생기는 예외가 있다.

2 5
9 9
5 9

종료 시간을 기준으로 정렬한다면 위와 같은 문제가 생긴다. end_time을 5, 다음에는 9로 변경되기 때문에 (5, 9)는 선택이 되지 않는다. 그렇기 때문에 만약 종료 시간이 같다면 시작 시간을 오름차순으로 정렬해주어야한다.

 

<최종코드>

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        int cnt = Integer.parseInt(br.readLine());
        int[][] times = new int[cnt][2];
		
        StringTokenizer st;
        for (int i=0; i<cnt; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            times[i][0] = Integer.parseInt(st.nextToken());
            times[i][1] = Integer.parseInt(st.nextToken());
        }
		
        // 종료 시간 기준으로 오름차순
        Arrays.sort(times, new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                // 종료 시간이 같다면 시작 시간이 빠른순으로 정렬
                if (o1[1] == o2[1]) return o1[0] - o2[0];
				
                return o1[1] - o2[1];
            }
        });
		
        int sum = 0;
        int end_time = 0;
        for (int i=0; i<cnt; i++) {
            if (end_time <= times[i][0]) {
                end_time = times[i][1];
                sum++;
            }
        }
        
        System.out.println(sum);
    }
}