[백준/1931번] 회의실 배정 [Java]

문제

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

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

---

풀이

풀이(1) -시간초과

 

   처음에 풀었을 때 다중배열 arr에 [n][2]로 담아준 뒤 시작시간을 중심으로 정렬한 뒤 시작시간이 같다면 끝나는 시간으로 정렬해주었다. 이 후 시작과 끝 값을 변수에 담고 끝나는 시간이 다음 번 배열의 시작시간보다 작으면 cnt++를 해주는 식으로 cnt를 계속 max값을 비교해 최대값을 찾는 방식으로 무식하게 모든 경우를 따져 주었다. 결과는 도출되지만 시간초과로 통과하지 못해 최적의 방법을 찾아야 했다. 

시간초과 때문에 아무래도 정답률이 낮은 것 같다.

package Practice;
import java.util.*;
import java.io.*;
 
 
public class Main {    
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine()); //testcase num
        String [][] arr = new String[n][2];
        
        for(int i=0;i<n;i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            arr[i][0]=st.nextToken();
            arr[i][1]=st.nextToken();
        } //입력
        
        Arrays.sort(arr,new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {                
                if(Integer.parseInt(o1[0])<Integer.parseInt(o2[0])) {
                    return -1;                                
                }    
                else if(Integer.parseInt(o1[0])==Integer.parseInt(o2[0])) {
                    return Integer.compare(Integer.parseInt(o1[1]),Integer.parseInt(o2[1]));
                }
                return 1;
            }
        });        
        //cnt세주기                
        int max=0;
        for(int i=0;i<n;i++) {
            int cnt=0;
            int begin= Integer.parseInt(arr[i][0]);
            int finish=Integer.parseInt(arr[i][1]);
            int j=i;
            
            while(true) {
                if(j==n-1) {
                    max= Math.max(max, cnt);                        
                    break;
                }
                if(finish<=Integer.parseInt(arr[j+1][0])) {                    
                    cnt++;
                    begin = Integer.parseInt(arr[j+1][0]);
                    finish = Integer.parseInt(arr[j+1][1]);
                    j++;                    
                    continue;
                }
                j++;
            }
        }
        System.out.println(max+1);
    }
 
    
}
 
 
 
 

 

 

풀이(2) -그리디 알고리즘(Greedy Algorithm)

 

  최적의 방법을 찾기위해서 생각해 봤을 때 Comparator에서 정렬을 할때 어차피 끝나는 시간은 시작시간보다 크므로 끝나는 시간에 따라 정렬하고 끝나는 값과 다음 시작시간 값을 비교하면 시간을 줄일 수 있을 것이라는 생각에 도달했다. o1과 o2의 끝값을 비교한 이후에 같으면 시작시간에 따라서 재정렬한 뒤 끝나는 시간이 다음 시작시간보다 작다면 cnt(카운트)를 1개 ++하고 end값을 해당 회의시간의 끝나는 시간으로 재설정해 주었다. 

 

package Practice;
import java.util.*;
import java.io.*;
 
 
public class Main {    
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine()); //testcase num
        int [][] arr = new int[n][2];
        
        for(int i=0;i<n;i++) {
            StringTokenizer 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) {                
                if(o1[1]==o2[1]) {
                    return Integer.compare(o1[0], o2[0]);                                
                }    
                return Integer.compare(o1[1], o2[1]);
            }
        });        
        //cnt세주기                        
        int end=-1;
        int cnt=0;
        for(int i=0;i<n;i++) {
            if(end<=arr[i][0]) {
                cnt++;
                end=arr[i][1];
            }
        }
        System.out.println(cnt);
        
    }
 
    
}
 
 
 
 
 
 
 

 

 

 

 

 

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

1931번: 회의실배정