[JAVA] 백준 1931 회의실 배정

[백준 1931]https://www.acmicpc.net/problem/1931

---

문제 조건

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아야 하는 문제

---

문제 입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

---

문제 풀기 전 설계

끝나는 시간 기준으로 정렬한 후 그리디 알고리즘으로 빨리 끝나는 순서로 고르면 최대가 될 것 같다.

---

문제 코드

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[][] meeting = new int[n][2];    // 시작 시간과 종료 시간을 담을 배열

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            meeting[i][0] = Integer.parseInt(st.nextToken());   // 시작 시간
            meeting[i][1] = Integer.parseInt(st.nextToken());   // 종료 시간
        }

        Arrays.sort(meeting, new Comparator<int[]>() {  // 2차원 배열을 정렬할 때는 Comparator 인터페이스를 사용
            // 인터페이스이기 때문에 그 내부의 메소드를 구현해야 함.
            @Override
            public int compare(int[] o1, int[] o2) {    // 2차원 배열에서 비교할 두 1차원 배열
                if (o1[1] == o2[1]) {   // 종료 시간이 같다면 시작 시간이 빠른 것부터
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];   // 그렇지 않다면 종료 시간이 빠른 것부터
            }
        });

        int endTime = 0;
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (meeting[i][0] >= endTime) { // 이전 종료 시간보다 시작 시간이 크거나 같으면 count++하고 종료시간 값 변경
                count++;
                endTime = meeting[i][1];
            }
        }

        System.out.println(count);
    }

}

---

문제 풀이

처음부터 종료 시각이 빠른 것만 고르면 그것이 최적 값이 되는 그리드 알고리즘 문제였다.
하지만 시작 시간과 종료 시간이 같은 값도 가능하기 때문에 종료 시간이 같다면 시작 시간이 먼저인 값을 선택해야 했다.
그렇기에 시작 시간과 종료 시간을 저장할 int형 2차원 배열을 생성하고 Comparator 인터페이스를 이용해 위에 서술한 조건대로 정렬한 후 시간이 겹치지 않는 값이 나올 때마다 count를 하나씩 증가시키면 된다.

---

Review

문제 풀이에 서술했던 조건 중 시작 시간과 종료 시간이 같은 값을 생각하지 않아서 한 번 틀렸던 문제다. 알고리즘 자체는 쉬웠지만 Comparator의 사용법을 복습할 수 있는 기회였다.