JAVA 백준 1931 회의실 배정 (정렬)

gamja00 2025. 5. 20. 02:22

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

문제

첫째 줄에 회의의 수 N ( 1 <= N <= 100000 ) 이 입력된다.
둘째 줄부터 N개의 줄에 각 회의 정보가 회의 시작 시간과 회의 종료 시간 ( 0 <= 시간 <= (2 ^ 31) - 1)을 공백으로 구분하여 주어진다.
회의는 한 번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. ( 끝나는 시간 <= 시작 시간 )
회의 시작과 끝나는 시간이 같다면 시작하자마자 끝나는 것으로 본다.
각 회의가 겹치지 않게 하면서 회의실을 최대로 사용할 수 있는 회의 최대의 개수를 출력하라.

초기 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public 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[][] list = new int[N][2];
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            list[i][0] = s;
            list[i][1] = e;

            min = Math.min(min, e);
        }

        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                } else {
                    return o1[1] - o2[1];
                }
            }
        });

        int result = 0;
        int index = 0;

        while (list[index][0] <= min) {
            int temp = index;
            int count = 0;
            int e = 0;

            while (temp < N) {
                if (e <= list[temp][0]) {
                    count++;
                    e = list[temp][1];
                }
                temp++;
            }
            result = Math.max(result, count);
            index++;
        }

        System.out.println(result);
    }
}

시작 시간을 먼저 정렬하고 시작 시간이 같을 때는 종료 시간이 작은 걸 먼저 오도록 정렬하고 앞에서부터 뒤로 계산하는 방식으로 했다.

시작 시간이 같을 땐 먼저 나오는 시간이 짧은 것으로 선택하여 다음으로 계속 진행하도록 했다.

예제는 맞게 나오는데 계속 틀렸다고 해서 반례를 찾아보니

시작시간 오름차순으로 정렬해놓았기 때문에 중간에 시간이 오래 걸리는 회의가 먼저 시작한단 이유로 선택되었기 때문에 회의를 더 여러번 할 수 있음에도 불구하고 먼저 시작하는 회의가 선택되는 것이었다.

다른 방법이 필요하다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public 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[][] list = new int[N][2];
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            list[i][0] = s;
            list[i][1] = e;
        }

        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[0] - o2[0];
                }
            }
        });

        int result = 0;
        int e = 0;

        for (int i = 0; i < N; i++) {
            if (e <= list[i][0]) {
                e = list[i][1];
                result++;
            }
        }

        System.out.println(result);
    }
}

이번에는 종료 시간 오름차순으로 정렬하여 정답을 구했다.

종료 시간 오름차순으로 정렬하고 종료 시간이 동일할 때는 시작 시간 오름차순으로 정렬할 수 있도록 했다.

이렇게 정렬하니 종료 시간을 기준으로 종료시간보다 크거나 같은 시작 시간을 가진 회의를 골라 해당 회의의 종료 시간으로 다시 과정을 반복하니 정답이 나와 여러 번 반복문을 돌리지 않아도 단 한 번에 문제가 풀렸다.

보통 문제는 먼저 수기로 풀어보고 코드를 작성하는 편인데

특히나 정렬이나 여러 자료 구조가 필요한 경우에는 수기로 풀어보는 게 더 구조를 알아내거나 풀이 방법을 알아내는 데에 용이한 것 같다.