백준 1931 회의실 배정 [JAVA]

문제 해석

• 첫번째 줄에 회의의 수(=N)를 입력 받는다. (=회의실을 예약하려는 횟수)

• 두번째 줄 부터 N(=회의의 수)개까지 해당 회의의 시작시간과 종료시간을 입력받는다.

• 그렇게 모두 입력 받았을 때 회의가 겹치지 않고 최대 몇 개의 회의를 할 수 있는 지 출력하면된다.

• 말로는 로직을 설명하기 어려워서 아래와 같이 그림으로 풀어보았다.

• 주어진 예시로 회의실 예약 신청 현황을 그리면 다음과 같다.
• 여기서 문제를 다시 생각해볼 필요가 있는데 문제는 최대 회의 개수를 구하라고 했다.
• 시작시간~종료시간이 짧은 것이 더 많은 회의를 넣기에 적합하다고 볼 수 있을 것이다.
• 겹치지 않는 회의에 대해 종료시간이 빠르면 더 많은 회의를 선택할 수 있다.
  
• 겹치지 않는 회의에 대해 종료시간이 빠른 것을 선택했을 때 위와 같이 총 4개가 나온다.
• A1(1~4), A4(5~7), A8(8~11), A11(12~14) 이렇게 최대 4개의 회의가 들어갈 수 있다.

코드

import java.io.*;
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[N][0] = 회의 시작 시간
        //int[N][1] = 회의 종료 시간
        int[][] schedule = new int[N][2]; // (시작시간, 종료시간)을 구현하기 위해 이차원 배열로

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

        br.close();

        //종료시간이 짧은 순으로 정렬해야 함. (단, 종료시간이 같을 경우에는 시작시간이 빠른 것)
        /* 종료시간이 같을 경우 시작 시간이 빠른 걸로 정렬해야 하는 이유.
            1  3
            6  7
            7  7
            이 있을 경우 1 ~ 3을 선택하고 그 다음 시작 시간은 3이 되었을 것이다.
            근데 여기서 시작시간이 빠른 걸로 선택을 안했다면
            1  3
            7  7
            6  7
            로 정렬된 경우
            다음 7~7로 인해 그 다음 시작 시간이 7이 되었을 거고 6 ~ 7은 충분히 들어갈 수 있음에도
            그 다음 시작 시간이 7이 되는 바람에 들어갈 수 없게 된다
            => 최대의 총 회의 개수를 구할 수 없게 된다.
         */
        Arrays.sort(schedule, new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {

                // 종료시간이 같을 경우 시작시간이 빠른순으로 정렬
                if(o1[1] == o2[1]) {
                    /*
                        [오름차순 정렬]
                        o1  > o2  => o1이 더 큼 => 정렬 시 o1이 o2의 뒤에 위치
                        o1 == o2  - return 0  : 순서를 변경X
                        o1  < o2  => o2가 더 큼 => 정렬 시 o2가 o1의 뒤에 위치
                    */
                    return o1[0] - o2[0];

                }

                return o1[1] - o2[1];
            }

        });


        int count = 0;
        int resetStartTime = 0;

        for(int i = 0; i < N; i++) {
            // 직전 종료시간이 다음 회의 시작 시간보다 작거나 같으면 회의 개수에 카운트 + 1
            if(resetStartTime <= schedule[i][0]) {
                resetStartTime = schedule[i][1];
                count++;
            }
        }

        System.out.println(count);

    }
}

결과

느낀 점

문제 자체는 생각보다 어렵지 않아서 풀 수 있었지만, compare()을 너무 오랜만에 써서 검색 후 사용할 수 있었다...ㅎ 분명 전에는 안보고도 작성할 수 있었는데 확실히 안쓰면 까먹는 것 같다. (복습의 중요성을 깨달음...)