[Java] 백준 1931 - 회의실 배정

 

Arrays.sort(meeting, (e1, e2) -> {
    if(e1[1]==e2[1]){
        return e1[0]-e2[0];
    }
    return e1[1] - e2[1];
});

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

1931번: 회의실 배정

시나리오

1. 입력으로 회의시간을 배열화

2. 배열의 1번 요소 즉, 회의 종료시간을 기준으로 정렬

3. 배열을 순회하며 기준인 회의의 종료시간보다 현재 회의 시작시간이 크거나 같다면 기준을 현재 회의로 변경하고 answer++

 

정답 코드

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

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

        int n = Integer.parseInt(br.readLine());
        int[][] meeting = new int[n][2];

        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            int[] cur = new int[2];
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 2; j++) {
                cur[j] = Integer.parseInt(st.nextToken());
            }

            meeting[i] = cur;
        }

        Arrays.sort(meeting, (e1, e2) -> {
            if(e1[1]==e2[1]){
                return e1[0]-e2[0];
            }
            return e1[1] - e2[1];
        });

        int criteria = 0;
        int answer = 1;

        for (int i = 1; i < n; i++) {
            if (meeting[criteria][1] <= meeting[i][0]) {
                criteria = i;
                answer++;
            }
        }

        System.out.println(answer);
    }
}

 

새로 알게된 점

시나리오의 2번 구현 시 Array.sort를 사용하여 e1, e2의 첫번째 요소만 비교하도록 했다. 하지만 오답처리를 받았고 이유를 알고보니 로직을 구현할 때 1번 요소가 같을 때 알아서 0번 요소 끼리 비교해 오름차순으로 정렬되는 것으로 착각해서였다.

분명 배운내용인데 다시 한번 바로잡고 갈 수있었던 기회가 되었다.

 

결론은  아래와 같이 구현해야한다는 것이다.

Arrays.sort(meeting, (e1, e2) -> {
    if(e1[1]==e2[1]){
        return e1[0]-e2[0];
    }
    return e1[1] - e2[1];
});

정리

가능한 최대 회의 횟수를 구해야 하므로 각 회의의 종료시간을 기준으로 정렬하는 게 중요한 아이디어였다. 

이렇게 시작과 끝이 주어지는 문제의 경우 위와 같은 풀이법이 사용되는 경우가 있으므로 유념해두자.