백준 No.1931 회의실 배정 - JAVA

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 긑나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

 

핵심코드

 

처음에 계속 시작시간을 기준으로 정렬을 시도하다가 답이 틀렸었다. 저번 강의실 배정과는 큰 차이가 있다. 이 문제는 한 회의실에서 겹치지 않는 회의의 개수를 파악하는 문제이다. 결국 한 회의실로 보고 풀어야 하는 문제다.

여기서 왜 끝나는 시간으로 정렬을 하는 걸까?

뒤에 if문을 보면 알 수 있지만 if문에서는 배열이 끝나는 시간으로 오름차순으로 정렬되어있다는 가정하에 계산해야 정확한 값이 나온다. 왜냐하면 prev_end 다음 인덱스를 바라볼 때 자신의 값보다 작은 값은 존재하지 않는다는 가정하에 값을 추려낸다. 

가장 핵심은 이 코드이고 이전 끝나는시간(prev_end) 가 다음 시작시간 시간 arr[i][0] 보다 작거나 같으면 한 회의실 안에서 회의가 한번 더 일아날 수 있다고 볼 수 있으므로 count가 +1된다. 해당 끝나는 시간은 정렬되어 있으므로 해당 if문을 들어왔을 경우 해당 회의에 끝나는 시간이 진행되므로 끝나는 시간이 다시 prev_end에 들어와야 한다. 그렇게 모든 배열을 다 돌아 한 회의실에서 진행할 수 있는 회의에 최대 개수가 출력된다.

 

디버깅

입력값

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

 

루프 첫번째(시작)  1시부터 4시가 들어오고 prev_end는 이제 4로 지정될 것이다. 그러면 한 회의가 진행되므로 count++

루프 두번째 

- 여기는 if문을 그냥 지나친다 두번째로 주어진 시작시간이 3이고 전에 끝나는 시간은 4이기에

루프 세번쨰

- 통과

루프 네번째

시작 시간이 전에 prev_end =4 보다 큰 값 5가 들어왔기 때문에 이제 여기서 prev_end 는 7이되고 count 는 1증가한다. 

(여기서 i 가 3인데 루프가 3번 다 돌고나서 모든 데이터 변화한 값을 보이기 위해 루프 디버깅을 루프 시작부분에 둠 결국 세번째 결과임 i는 신경 안 써도 됨)

 

이런식으로 계속해서 돌고 돌아 결국 4가 나온다.

 

 

package com.example.algorithgm.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Greedy2 {

        public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                int N = Integer.parseInt(br.readLine());
                int 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());
                }

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

                        @Override
                        public int compare(int[] o1,int[] o2){
                                return o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1];
                        }
                });

                int prev_end = 0;
                int count = 0;

                for (int i =0;i<N;i++){
                        if(prev_end <= arr[i][0]){       //한 회의실에서 몇개나 할 ㅅ 있는지
                                 prev_end = arr[i][1];
                                 count++;  //4시 4시바톤터치도 가능
                        }
                }
                System.out.println(count);




        }
}