[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)

* Greedy 알고리즘 (탐욕적 알고리즘)

완전탐색 , 동적 계획법 --> 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는다.

그리디 알고리즘 --> 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 

     즉, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.

따라서 알고리즘의 정당성을 증명하는 과정이 필수적이다.!

문제보기 >> 백준 1931 : 회의실배정 

가장 먼저 끝나는 회의를 선택하고, 이 회의와 겹치지 않는 회의중 가장 먼저 끝나는 회의를 선택하는 것을 반복한다.

((정당성의 증명))

" 가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재한다." 를 증명해보자.

S는 회의 목록, Smin 은 가장 일찍 끝나는 회의.

S의 최적해 중 Smin을 포함하지 않는 답이 있다고 가정하자

이 답은 서로 겹치지 않는 회의의 목록이다.

이 목록에서 첫번째로 개최되는 회의를 지우고 Smin 을 추가해 새로운 목록을 만든다.

Smin은 S에서 가장 일찍 끝나는 회의의기 때문에, 지워진 회의는 Smin보다 일찍 끝날수 없다.

따라서 두번쨰 회의와 Smin이 겹치는 일은 없으며, 새로 만든 목록도 최적해가 될 수 있다.

==> 항상 Smin을 포함하는 최적해는 존재한다.

==> 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없다.

import java.awt.Point;
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_1931 {
    //회의실배정
    static int N;
    static int[][] arr;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(bf.readLine());
        arr=new int[N][2];
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr,new Comparator<int[]>() {
            //0 : o1==o2
            //1 : o1>o2
            //-1 : o1<o2
            //arr[n][1]을 기준으로 오름차순 정렬
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o2[1]==o1[1]) {
                    return o1[0]-o2[0];
                }
                else return o1[1]-o2[1];
        
            
            }
        });
    
    
        
 
        System.out.println(solve());
        
    
    }
    
    static int solve(){
        
        int now=0;
        int cnt=1;
        
        for(int i=1;i<N;i++) {
            //다음 회의의 시작시간이 현재 회의의 종료시간보다 작으면 continue
            if(arr[i][0]<arr[now][1]) continue;
        
            cnt++;
            now=i;
        }
        
        
        return cnt;
 
        
    }//end of solve
 
}
 

++) 고민해야할 예외 상황

2

2 2

1 2

와같은 입력이 있다면,

(1 2) -> (2 2) 

의 순서로 회의실 배정을 할 수 있고 답은 2일것이다.

하지만 회의 종료시간만을 기준으로 data를 정렬하면

(2 2) 가 우선 순위가 되어 (1 2) 배정은 불가능하다고 판단할수도 있다.

따라서 정렬 과정에서,

회의 종료시간이 같다면, 회의 시작시간을 기준으로 한 오름차순 정렬을 해줘야한다.