[인프런 자바/java] 2. 회의실 배정 _디버깅의 눈물

체크 포인트

 

1. 그리디 알고리즘(Greedy Algorithm) 이용

 

-현재의 가장 최적의 답을 선택해 적합한 결과를 도출해내는 '그리디 알고리즘'을 이용하는 문제이다.

-그리디 알고리즘의 대표적 문제 유형으로는 활동 선택 문제나 거스름돈 문제 등이 있다.

 

-회의실 배정과 같은 문제가 대표적인 활동 선택 문제 유형에 속한다. 한번에 하나의 활동만 처리할 수 있는 상황에서 가장 많은 활동을 처리할 수 있도록 하는 것이다.

 

 

 

 

2. 회의 종료 시간이 빠른 순으로 정렬

 

-가장 많은 회의를 진행하려면, 회의 종료 시간이 가장 빠른 순서로 정렬해야 한다.

 

1)회의 종료 시간을 기준으로 오름차순 정렬을 하고 종료시간이 가장 빠른 회의를 진행시킨다.

2)해당 회의가 끝났을 때, 새로운 회의 시작 시간이 이전 회의 종료시간 보다 크거나 같고,

3)가장 빠른 회의 시작 시간을 찾아 진행한다면, 최대 회의 수를 구할 수 있다.

 

 

 

// 예시 1
// 회의 종료 시간을 기준으로 정렬 전
1 4
2 3
3 5
4 6
5 7

// 회의 종료 시간을 기준으로 정렬 후
2 3
1 4
3 5
4 6
5 7

 

 

-예시1)을 예로 들어보자.

 

1)회의 종료 시간을 기준으로 오름차순 정렬을 한다면 (2 3), (1 4), (3 5), (4 6), (5 7)의 순서가 된다.

2)첫번째 회의는 2에 시작하고 3에 끝난다.

3)해당 회의가 끝났을 때, 가장 빨리 시작할 수 있는 다음 회의는 (3 5)이다.

4)두번째 회의는 3에 시작하고 5에 끝난다.

5)해당 회의가 끝났을 때 가장 빨리 시작할 수 있는 다음 회의는 (5 7)이다.

6)세번째 회의는 5에 시작하고 7에 끝난다.

7)더 이상 진행할 수 있는 회의가 없으므로 최대 진행 가능 회의 수는 3이다.

 

 

 

-위의 추론 과정을 수식화 한다면 다음과 같다.

 

1)정렬 과정

// 회의 시작/종료 시간을 담은 2차원 배열의 오름차순 정렬
    
Arrays.sort(meeting, new Comparator<Integer[]>() {

    @Override
    public int compare(Integer[] o1, Integer[] o2) {
        // 회의 종료 시간이 빠른 순으로 정렬
        if(o1[1] - o2[1]>0){
            return 1;
        }
        else if(o1[1] - o2[1]<0){
            return -1;
        }

        // 회의 종료 시간이 동일하다면,
        else{
            // 회의 시작 시간을 기준으로 오름차순 정렬
            if(o1[0] - o2[0]<0){
                return -1;
            }
            else{
                return 1;
            }
        }
    }
});

 

 

 

 

2) 이전 회의 종료 시간과 현재 회의 시작 시간 비교

 

 

		// 전체 회의의 수
		int count = 0;
		// 첫번째 회의 수 1 추가
		count++;
		
		// 이전 회의 종료 시간
		int prevEnd = meeting[0][1];
		
		// 2번째 회의부터 탐색
		for(int i=1; i<N; i++){
			
			// 현재 진행할 회의의 시작 시간이 이전 회의의 종료시간보다 크거나 같다면,
			if(meeting[i][0]>=prevEnd){
				// 회의 진행 +1
				count++;
				// 이전 회의의 종료 시간 = 현재 회의의 종료시간
				prevEnd = meeting[i][1];
			}
			
		}

 

 

 

 

 

 

P.S-2차원 배열의 정렬의 경우 아래 링크를 참조하면 확인할 수 있다.

 

https://tears-of-debugging.tistory.com/54

[java(자바)] 2차원 배열 정렬하기 Comparator, 람다식 _디버깅의 눈물

 

 

 

 

 

 

 

 

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


class Main{
	
	static Integer[][] meeting;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		Integer N = Integer.parseInt(st.nextToken());
		
		meeting = new Integer[N][2];
		
		for(int i=0; i<N; i++){
			st = new StringTokenizer(br.readLine(), " ");
			
			meeting[i][0] = Integer.parseInt(st.nextToken());
			meeting[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(meeting, new Comparator<Integer[]>() {

			@Override
			public int compare(Integer[] o1, Integer[] o2) {
				// 회의 종료 시간이 빠른 순으로 정렬
				if(o1[1] - o2[1]>0){
					return 1;
				}
				else if(o1[1] - o2[1]<0){
					return -1;
				}
				
				// 회의 종료 시간이 동일하다면,
				else{
					// 회의 시작 시간을 기준으로 오름차순 정렬
					if(o1[0] - o2[0]<0){
						return -1;
					}
					else{
						return 1;
					}
				}
			}
		});
		
		
		solution(N);
		
	}// end of main
	
	
	
	static void solution(int N) {

		// 전체 회의의 수
		int count = 0;
		// 첫번째 회의 수 1 추가
		count++;
		
		// 이전 회의 종료 시간
		int prevEnd = meeting[0][1];
		
		// 2번째 회의부터 탐색
		for(int i=1; i<N; i++){
			
			// 현재 진행할 회의의 시작 시간이 이전 회의의 종료시간보다 크거나 같다면,
			if(meeting[i][0]>=prevEnd){
				// 회의 진행 +1
				count++;
				// 이전 회의의 종료 시간 = 현재 회의의 종료시간
				prevEnd = meeting[i][1];
			}
			
		}
		
		
		System.out.println(count);
		
	}
	
	
	
} // end of Main