백준(BOJ)-1931 회의실 배정[JAVA] (그리디 알고리즘)

문제

문제 이해

우선, 문제를 읽고 생각을 해보았는데, 밑에 힌트를 보면 (1,4) , (5,7), (8,11), (12,14)를 이용할 수 있다고 되어있다. 입력 값을 그림으로 그려보았다.

악필...

 

그림을 보고 생각을 해봤는데, 0~14 시까지 시간이 흘러감에 따라 중복된 시간에서의 여러개의 회의실 사용은 불가능 하다. 즉, cur(현재 시간)이 첫번째 방이 시작하는 회의실 시작 시간을 시작으로, 끝났을때 시간 을 다시 cur에다가 넣어주면 cur는 회의의 시작과 종료진행사항을 알 수 있다. 

ex)1~4시에 회의실을 먼저 사용하면, cur=4가 되므로, 4이후에 시작하는 회의실밖에 선택할 수 없음.

 

코드 

이를 코드로 짜보면,

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int room_time[][] = new int[N][2];

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

        for(int i=0;i<N;i++)
        {
            if(room_time[i][0]>=cur)
            {
                cur = room_time[i][1];
                count++;
            }
        }

        System.out.println(count);
    }
}

와 같이 된다. 하지만, 이코드에서는 현재 입력값이 1 4 -> 3 5 -> 0 6 이런식으로 입력을 받기때문에 처음에 무조건 1시부터 방을 사용하도록 된다. 만약 입력값의 순서가 바뀌더라도 똑같은 정답을 나오기 위해서 고민한 결과 현재의 코드에서 이차원 배열로 되어있는 시작시간과, 종료시간중 종료시간을 오름차순으로 정렬해주어야 한다.

 

2차원 배열의 정렬은 다음과 같다.

 

https://netco97.tistory.com/48

[JAVA] JAVA 2차원 배열 정렬 (Comparator, Lamda)

이전글에다가 포스팅 한 글인데 이를 토대로 하면, 

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

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

                // 종료시간이 같을 경우 시작시간이 빠른순으로 정렬해야한다.
                if(o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }

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

        });

와 같이, o1[1] - o2[1]이 의미하는것은 종료시간을 오름차순 하는 의미이고, 만약 종료시간이 같다면(if(o1[1]==o2[1])) 시작시간순으로 다시 오름차순을 해주면 된다.

 

총 코드

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int room_time[][] = new int[N][2];

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

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

                // 종료시간이 같을 경우 시작시간이 빠른순으로 정렬해야한다.
                if(o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }

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

        });

        int cur =0;
        int count = 0;

        for(int i=0;i<N;i++)
        {
            if(room_time[i][0]>=cur)
            {
                cur = room_time[i][1];
                count++;
            }
        }

        System.out.println(count);
    }
}

후기

처음에 그림을 그리고, 알고리즘에 대해서는 생각보다 빠르게 접근을 했지만, 2차원 배열의 정렬방법을 접근하기가 힘들어서 오래걸린 문제였다. 다음에는 빠르게 풀수 있을 것 같다.