[java 백준] 실버 2/1931번 회의실 배정

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

1931번: 회의실 배정

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static int cnt;
    public static int[][] arr;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][2];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
 
        }
 
        // 종료시간을 기준으로 정렬
        // 나는 시작시간을 기준으로 정렬했고, comparator생각도 못함
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    // 종료시간이 같을 경우 시작시간이 더 빠른 애
                    return Integer.compare(o1[0], o2[0]);
                }
                return Integer.compare(o1[1], o2[1]);
            }
        });
        int std = arr[0][1];
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i][0] >= std) {
                // 어차피 정렬되어있어서 상관없음
                cnt++;
                std = arr[i][1];
            }
        }
        System.out.println(cnt);
 
    }
 
}

int std = arr[0][1];

        int cnt = 1;

        for (int i = 1; i < n; i++) {

            if (arr[i][0] >= std) {

                // 어차피 정렬되어있어서 상관없음

                cnt++;

                std = arr[i][1];

            }

        }

이 코드들 때문이다. 우선 기준이 되는 첫번째 종료시간을 설정하고 

시작시간이 std보다 크면 그 시작시간에 해당하는 종료시간이 std가 되는 형태로 코드를 짜봤다. 여기서 종료시간이 같다면 시작시간이 더 작은애를 앞에 두는 이유를 설명할 수 있다.

std는 반복문을 통해 arr[i][0]이 자기보다 큰지 작은지 비교하는데 만약에 종료시간이 같은데 시작시간이 더 작은애가 뒤에 있다면 얘랑 비교하는걸 놓칠 수도 있기 때문이다.

 

예를 들어

 

1 4

3 5

0 6

7 7

5 7

이 있다고 해보자. 종료시간만 정렬되어있다면

 

 

1 4

3 5

0 6

7 7

5 7일테고

여기서는 (1,4)  (7,7)만 탐색하고 끝낼거지만

 

종료시간이 같을 때 시작시간도 같이 고려해준다면

1 4

3 5

0 6

5 7

7 7로 정렬되기 때문에 (1,4) (5,7) (7,7) 총 3가지 경우가 생긴다. 

 

기억해야할 것 

배열 안에 있는 원소 Comparator를 이용해 비교시

 

Arrays.sort(arr,new Comparator<int[]>(){

 

});

반드시 import java.util.Comparator 해줘야함!