[JAVA] 백준 (실버1) 1931번 회의실 배정

AIR·2024년 3월 20일

코딩 테스트 문제 풀이

목록 보기

61/135

링크

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

문제 설명

정답률 30.475%
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력 예제

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

출력 예제

풀이

서로 겹치지 않는 시간에 대해 종료 시간이 빠르면 선택할 수 있는 시간이 많아진다. 그러므로 종료 시간에 대해서 정렬을 하고 종료 시간에 겹쳐지는 시간을 제외하여 카운트한다.

하지만 (1, 4), (4, 8), (8, 8)의 경우에 만약 종료 시간으로만 정렬을 하면 다음과 같이 정렬된다.

(1, 4), (8, 8), (4, 8)

이렇게 정렬되면 (1, 4), (8, 8)만 선택되어 (4, 8)이 생략될수 있으므로 같은 종료 시간에 대해 시작 시간도 정렬을 해야한다.

Arrays.sort(time, Comparator
        .comparingInt((int[] o) -> o[1])
        .thenComparingInt((int[] o) -> o[0]));

코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] time = new int[N][2];
        StringTokenizer st;

        //입력값 세팅
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            time[i][0] = Integer.parseInt(st.nextToken());
            time[i][1] = Integer.parseInt(st.nextToken());
        }

        //time 배열 정렬
        Arrays.sort(time, Comparator
                .comparingInt((int[] o) -> o[1])  //종료 시간에 대해 정렬
                .thenComparingInt((int[] o) -> o[0]));  //종료 시간이 같을 경우 시작 시간으로 정렬

        int count = 0;
        int beforeEnd = 0;

        for (int i = 0; i < N; i++) {
            int start = time[i][0];
            int end = time[i][1];

            //시작 시간이 이전 끝시간보다 크거나 같으면 갱신 및 카운트
            if (beforeEnd <= start) {
                beforeEnd = end;
                count++;
            }
        }

        System.out.println(count);
    }
}

정리

시간표를 최대한 많이 배정하거나 선택하는 문제를 '활동 선택 문제(Activity Selection problem)'라고 한다. 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제이다. 여기서는 각 회의가 겹치지 않게 최대한 많은 회의를 배정하는 것으로 나와있다.

하나의 활동을 완료하기 전까지는 다른 활동을 선택할 수 없다. 즉, 하나의 활동을 선택하면 나머지 겹치지 않는 활동에 대해서 독립적이고, 탐욕 선택이 결과에 영향을 미치지 않는다.

처음에는 모든 경우에 수에 대해서 고려하려 했으나 그렇게 되면 이중 반복문으로 시간복잡도가 $O(n^2)$ 이 되어서 N의 최댓값이 100,000이기 때문에 10억의 연산이 나와 시간 초과가 나왔다. 이 문제는 그리디 알고리즘 문제로 모든 경우의 수를 따지면 안된다.