(Java) 백준 1931 - 회의실 배정

처음에는 완전 탐색으로 구현하려고 했는데 코드를 작성하다 막혀서 포기하고

문제 유형을 확인했는데 그리디, 정렬이었다.

감을 잡을 수가 없어서 검색을 통해 힌트를 얻고 풀었다.

종료시간을 기준으로 정렬하게 되면 겹치는 회의와 겹치지 않는 회의를 알 수 있고

겹치지 않는 회의 중 가장 빠르게 끝나는 회의를 선택하면 된다.

문제가 그리디를 사용한다는 걸 파악하기 어려웠고, 정렬 또한 생각하기 어러웠다.

 

최종 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        int cnt = 0;
        int preEnd = 0;
        // 압력값 배열에 삽입
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 정렬 (람다 사용)
        Arrays.sort(arr, (o1, o2) -> {
            // 종료시간이 같은 경우 시작시간을 기준으로 오름차순 정렬
            if(o1[1] == o2[1]) {
                return o1[0] - o2[0];
            }
            // 종료 시간을 기준으로 오름차순 정렬
         return o1[1] - o2[1];
        });
        // 정렬후 카운팅
        for (int i = 0; i < n; i++) {
            if(preEnd <= arr[i][0]) {
                preEnd = arr[i][1];
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}