[백준알고리즘-JAVA]1931번 풀이(회의실 배정) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1931번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

 그리디 알고리즘에서 가장 유명한 문제죠 회의실 시간을 배정해주는 알고리즘입니다. 이번 알고리즘에서 중요한 점은 바로 어떻게 회의시간을 조절할 것인가에 집중해서 STEP을 따락 보시면 됩니다.

---

백준 1931 (회의실 배정)

문제

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

입력

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

출력

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

입력 예제

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

출력 예제

4

실패 코드

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

public class Main {

	static long ans = Integer.MIN_VALUE;
	static int N;
	
	static int[][] arr;
	static int[] dp;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		arr = new int[N][2];
		dp = new int[N];
		
		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[]>() {
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		
		/*for(int i = 0 ;i < N ; i++) {
			for(int j = 0 ;j < 2 ; j++)
				System.out.print(arr[i][j] + " ");
		System.out.println();
		}*/
		
		int time = 0;
		
		for(int i = 0 ; i < N ;i++) {
			time = arr[i][0]+arr[0][0];
			dp[i] += 1;
			for(int j = i + 1 ; j < N ; j++) {
				if(arr[j][0] >= time) {
					time = arr[j][0] + arr[j][1];
					dp[i] += 1;
				}
			}
		}
		
		for(int i : dp)
			ans = Math.max(ans, i);

		System.out.println(ans);
		
		}
	
}

일단은 떠오르는 대로 시간을 조정하여봤습니다. 2차원 배열로 하여 시작시간으로 정렬을 한 뒤에 가능한 시간들을 더해주었습니다. 이럴 경우 답은 맞지만 시간 초과라는 문제가 생기게 됩니다. 2차원 배열로 중첩 반복문을 2번이나 사용하기 때문이죠.

 

성공 코드

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

public class Main {

	static long ans = Integer.MIN_VALUE;
	static int N;
	
	static int[][] arr;
	static int[] dp;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		arr = new int[N][2];
		dp = new int[N];
		
		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[]>() {
			public int compare(int[] o1, int[] o2) {
				
				if(o1[1] == o2[1])
					return o1[0] - o2[0];
				
				return o1[1] - o2[1];
			}
		});
		
		/*for(int i = 0 ;i < N ; i++) {
			for(int j = 0 ;j < 2 ; j++)
				System.out.print(arr[i][j] + " ");
		System.out.println();
		}*/
		
		int time = 0;
		int end = 0;
		
		for(int i = 0 ; i < N ;i++) {
			if(end <= arr[i][0]) {
				time++;
			end = arr[i][1];
			}
		}

		System.out.println(time);
		
		}
	
}

성공코드의 핵심은 바로 끝나는 시간으로 정렬하여 해결해주는 방법입니다.

---

알고리즘 흐름도

입력받기 -> 정렬하기 -> 끝나는 시간을 기준으로 반복문 돌리기 -> 출력하기

---

STEP1 출발시간 정렬과 끝나는 시간 정렬의 차이

 

이번 알고리즘을 풀면서 출발시간으로 정렬하기 위 끝나는 시간으로 정렬하는 것의 차이를 생각해 보았습니다. 출발 시간으로 정렬하게 된다면, 끝나는 시간이 만약에 엄청나게 길어진다면, 먼저 시작해도 최대한 많은 회의를 할 수 없다는 것을 알 수 있습니다.

 

 즉, 끝나는 시간을 알 수 없기에 추가적으로 반복문을 통해 끝나는 시간까지 고려해 줘야 하기 때문에 더 많은 시간이 걸리게 됩니다.

 

 이번 알고리즘의 핵심은 바로 끝나는 시간으로 정렬을 하여 1번의 반복문으로 시간 초과의 문제를 해결해야 했습니다.

 

 물론 처음부터 정렬이 생각나지 않으신 분들도 있습니다. 그러한 분들은 많은 문제를 풀어보거나 또한 이런 식으로 시간에 따라 맞춰서 넣는 문제, 줄을 이었을 경우 겹치지 않아야 되는 문제와 같은 알고리즘을 만날 때는 정렬방법부터 생각해보시는 것도 좋은 방법입니다.

 

---

STEP2 2차원 배열 정렬하기

2차원 배열 정렬은 아직도 모르신다면, 그냥 외우시는 게 빠릅니다.

 

자주 쓰이며, 정렬에 기본을 파악하기에 아주 좋기 때문이죠

Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				
				if(o1[1] == o2[1])
					return o1[0] - o2[0];
				
				return o1[1] - o2[1];
			}
		});

 

언제나 그렇듯이 이것을 번역(?) 해본다면 이런 의미입니다.

 

2차원 배열 arr을 정렬한다.

 

새로운 Comparator객체를 생성하는데 제네릭으로 1차원 int 배열을 한다고 명시한다.

 

compare을 오버 라이딩하여 각 인자로 o1, o2 1차원 배열을 인자로 넘겨준다.

(이때 o1, o2는 각각 배열의 첫 번째를 의미합니다. )

o1의 배열에는 arr [0][1] o2배열에는 arr [1][0] 과같이 서로 행이 다른 값을 의미하죠

 

반환 값으로 o1과 o2의 차이를 반환합니다. 이때 음수이면 o2가 큰 수이고 양수이면 o1이 양수임으로 이로 인해 Arrays.sort에서 자동적으로 정렬을 해주죠

 

그런데! 여기서 하나의 if문이 보이죠

if문을 해준 이유는 만약에 회의가 끝나는 시간이 같다면 시작시간이 작은 값이 앞에 오도록 하는 메서드입니다.

 

여기서 각 인덱스 [0]은 시작 시간 [1]은 끝나는 시간을 의미하게 되죠

---

STEP 3 끝나는 시간을 기준으로 비교하여 답 도출하기

 이제 회의 종료시간으로 정렬을 하였다면, 답을 도출하기 한결 편해집니다.

 

int time = 0;
		int end = 0;
		
		for(int i = 0 ; i < N ;i++) {
			if(end <= arr[i][0]) {
				time++;
			end = arr[i][1];
			}
		}

time은 우리가 구하려는 회의의 개수를 의미

end는 끝나는 시간을 의미하죠

 

반복문을 통해서 정렬한 값들을 비교합니다.

 

end보다 arr [i][0]이 크다면, (즉, 현재 끝나는 시간이 시작시간보다 작다면 그 회의는 겹치지 않고 회의를 진행할 수 있죠)

 

그렇다면 회의의 개수 time을 +1을 해주고

끝나는 시간을 그 회의가 끝나는 시간으로 지정해줍니다.

 

뭐.. 이런 말로 이해가 어렵다면, 역시나 입력 예제를 통해서 하나씩 대입해보면 이해가 가장 쉽습니다.

 

우선 정렬된 입력은 아래와 같습니다.

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

이미 잘 정렬이 되어있죠? 이럴 경우 정렬은 딱히 고려되지 않아도 되죠

 

그러면 하나씩 해보면 처음 1, 4가 들어온다면

 

if문에 걸립니다.

time = 1

end = 4 가 걸립니다.

 

다음 인덱스로 넘어갑니다. (i = 1)

이번에는 arr [1][0]이 3 임으로 if문에 걸리지 않습니다.

 

당므 인덱스로 넘어갑니다. (i=2)

이 또한 if문에 걸리지 않습니다.

 

다음 인덱스로 넘어갑니다. (i=2

네 이번에는 if문에 걸리게 되죠

time = 2

end = 7 이 담기게 되죠

 

이런 식으로 쭉 이어지면 결과적으로 

(1, 4) / (5, 7) / (8, 11) / (12, 14)

이렇게 4개가 담기고

time =4

end = 14

로 반복문이 끝난 후 time을 출력만 해주면 끝!