Baekjoon1931*: 회의실 배정, 시간 초과와 그리디 알고리즘

문제

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

입력

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

출력

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

 

풀이1

제한조건을 확인한다. 시작시간과 끝나는 시간의 최대 간격은 2의 31승으로 매우 커보이지만 int의 최대범위다. 회의의 수는 10만까지 가능하고 주어진 회의시간들은 오름차순 또한 아니다.

동적계획법을 활용하여 매 항마다 최대 회의시간을 기록한다. 현재항 i에서 자기보다 이전항 중 시간이 겹치지 않는 회의를 찾는다.

시간이 겹치지 않는 회의 중 최대값을 가져와 1을 더한다

1	4	1
3	5	1
0	6	1
5	7	2
3	8	1
5	9	2

import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] dp = new int[N+1][3];
		dp[0][2]=0;
		for(int i=1;i<N+1;i++){
			dp[i][0]=sc.nextInt();
			dp[i][1]=sc.nextInt();
			for(int j=0;j<i;j++) {
				if(dp[i][0]>=dp[j][1] || dp[i][1]<=dp[j][0]) {
					dp[i][2]=Math.max(dp[i][2], dp[j][2]+1);
                }}}
		System.out.print(dp[N][2]);
    }}

*시간 초과가 나온다. 이러한 동적 계획법을 보완하기 위해 그리디 알고리즘을 사용한다고 한다.

 

풀이2

그리드 알고리즘의 활동 선택 문제(Activity Selection problem) 유형이다. 위와 같이 동적계획법을 통해 최대값을 계속 구해나가며 구할 수 있지만 시간이 오래걸린다는 단점이 존재한다. 이를 더 단순화하기 위해 회의가 가장 먼저 끝나는 순서대로 정렬한 뒤 회의들을 이어 붙이는 식으로 한다.

[ 가장 먼저 끝나는 회의를 선택 ] →[ 그 뒤에 겹치지 않으면서 가장 먼저 끝나는 회의를 선택 ]을 반복하는 것이다.

이를 위해 정렬을 해야하는데, 이중배열의 정렬은 Arrays.sort의 compare을 사용한다.

정렬을 한 후에는 이미 시간 순으로 나열되어있기 때문에 반복문을 한 번 돌리면서 값을 구할 수 있게 된다.

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] arr = new int[N][2];
		int sum=0;
		int left=0;
		for(int i=0; i<N;i++) {
			arr[i][0]=sc.nextInt();
			arr[i][1]=sc.nextInt(); //배열에 값을 넣어준다
		}
		Arrays.sort(arr, (o1, o2) -> { //정렬하는 코드
			if(o1[1] == o2[1]) {
		    return Integer.compare(o1[0],o2[0]);}
		else{
			return Integer.compare(o1[1],o2[1]); } });
	
    for(int i=0; i<N;i++) {
			if(arr[i][0]>=left) { //어차피 끝나는 시간 순차적으로 배열되어있기 때문에
				left=arr[i][1];   //오른쪽으로 가면서 겹치지 않는 구간을 만나면 바로 추가해준다
				sum++;
			}
	}
	System.out.print(sum);
    }}