[JAVA] BOJ(백준) - 회의실 배정 - 1931번

문제내용

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

1931번: 회의실 배정

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

입력

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

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

---

문제 접근 방법

강의를 들을 수 있는 최대개수, 회의의 최대 개수 등등.. 같은 문제는 그리디 알고리즘의 대표적인 문제같다.

여튼 회의의 최대 개수를 출력하기 위해선 끝나는 시간이 가장 빠른 순서대로 회의를 진행하는게 좋다.

이유는 회의가 빨리끝나야 남은 시간에서 더많은 회의를 진행할 수 있기 때문이다.

 

그렇다면 회의가 가장 빨리 끝나는 시간은 어떻게 골라 낼지 생각해보면 된다.

우선 입력받은 회의시간을 2차원 배열인 arr에 저장해야 한다.

이때 arr배열은 arr[회의][0] = 회의 시작시간, arr[회의][1] = 회의 끝나는 시간 으로 정의 해주면된다.

그리고 회의시간을 arr에 입력 받았다면 문제에서 오름차순 정렬을 안해주기 때문에 끝나는 시간 순으로 오름차순 정렬을 해줘야한다. 주의할점은 끝나는 시간으로 정렬할때 끝나는 시간이 같다면 시작시간 순으로 한번더 오름차순 정렬해줘야 한다는 것이다.

 

예를 들어 아래처럼 입력받고 끝나는 시간으로 정렬한 결과를 보면

1	4	정렬 후 ->	1	4
7	7		3	5
3	5		0	6
0	6		7	7
5	7		5	7
7	7		7	7
7	7		7	7

위와 같이 나온다.  위에 표처럼 정렬후 답을 구한다면

정답은 4가 나오는데 실제정답은 (5,7)을 포함한 5라는걸 알 수 있다.

이런 반례가 존재하기 때문에 끝나는 시간이 같을땐 시작시간으로 오름 차순으로 정렬해줘야한다.

 

arr을 정렬 했다면 이젠 회의 개수만큼(0~N)까지 순회하면서

회의 시작시간 >= 이전 회의 끝나는 시간 일때만 회의 개수를 카운트 해주면 풀리는 문제이다.

 

참고로 2차원 배열 정렬같은 특별한 기준에 의해 정렬하는 방법은 Compartor를 사용하면되는데 Comprator를 사용하는 문제중 백준의 https://www.acmicpc.net/problem/11286 이문제를 참고해보는 것도 좋은 방법이라 생각한다.

 

풀이를 보자.

 

---

풀이

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 {
	static int[][] arr; //arr[회의][0]=시작시간, arr[회의][1]=끝나는시간
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		arr = new int[N][2];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<2; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		Arrays.sort(arr, new Comparator<int[]>() {
			
			//끝나는 시간 순으로 정렬
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1]>o2[1]) return 1;
				else if(o1[1]<o2[1]) return -1;
				else {//만약 끝나는 시간이 같다면 시작시간 순으로 정렬
					if(o1[0]>o2[0]) return 1;
					else if(o1[0]<o2[0]) return -1;
					else return 0;
				}
			}
		});
		
		int answer = 1;//첫번째 회의 count
		int temp = arr[0][1];//이전 회의 끝나는 시간
		for(int i=1; i<N; i++) {
			if(arr[i][0]>=temp) {
				answer++;
				temp=arr[i][1];
			}	
		}
		System.out.println(answer);
	}
}

 

---

마치며

이문제는 Comparator만 잘쓴다면 쉽게 풀수 있는 문제라고 생각한다.

참고로 이문제에선 Comparator 사용시 반환값을 선행요소 - 후행요소(o1[1]-o2[1]) 를 활용해 간단하게 해도 되지만 기본적으로 Underflow, Overflow가 발생할수 있기때문에 대소비교를 통해 하는것이 안전하다.