[백준] 1931번 : 회의실배정 - JAVA [자바]

www.acmicpc.net/problem/1931

1931번: 회의실배정

 

---

• 문제

 

 

 

 

그리디 알고리즘의 대표적인 문제 중 하나다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

위와 같이 시간표를 최대한 많이 배정하거나 선택하는 문제를 '활동 선택 문제(Activity Selection problem)'라고 한다. 간단하게 설명하자면, 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제다. 위에서는 각 회의가 겹치지 않게 최대한 많은 회의를 배정하는 것으로 나와있다.

 

이러한 문제들의 특징은 '한 사람이 하나의 활동에 대해서만 작업할 수 있다'라는 점이다. 즉, 하나의 활동을 완료하기 전까지는 다른 활동을 선택할 수 없다는 것이다. 즉, 하나의 활동을 선택하면 나머지 겹치지 않는 활동에 대해서 독립적이고, 이전 포스팅에서 말했던 것처럼 '탐욕 선택이 이후의 결과에 영향을 미치지 않는다.'

 

위의 자세한 증명은 아래 링크에서 매우 잘 설명하고 있으니 한 번 참고해보시길 바란다.

en.wikipedia.org/wiki/Activity_selection_problem

Activity selection problem - Wikipedia

 

 

 

 

그럼 이제 어떻게 그리디 알고리즘을 적용하는가의 문제만 남았다.

 

한 번 생각해보자. 이전의 선택 결과가 이후의 결과에 영향을 미치지 않으려면 먼저 '이전 선택의 종료 시간'과 '이후 선택의 시작 시간'이 서로 겹치지 않으면 된다. 그리고 최대한 많은 활동을 선택하려면 종료시간이 빨라야 할 수 밖에 없을 것이다.

 

쉽게 말하자면 서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다는 것이다.

 

위의 문제를 토대로 한 번 풀어보자. 주어진 값들을 그래프로 그리면 다음과 같다.

 

 

 

이렇게만 보면 하나하나 고르면서 모든 경우의 수를 대입해보고 그 중 선택 가능한 최대 개수를 구해야 할 것 같지만, 앞서 말했듯 서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다는 것에 포인트를 맞춰보면 매우 쉽게 풀린다는 것을 볼 수 있다.

 

바로 종료시간을 기준으로 정렬을 하는 것이다. 그런 다음 이전 종료시간에 대해 겹치는 것들은 제외하고 남은 것들 중 선택하면 된다는 것이다.

 

말로하면 어려우니 위 그림을 다시 종료시간을 기준으로 정렬해보면 다음과 같다.

 

 

 

 

 

이렇게 정렬하고, 빨리 끝나는 것을 선택해본다. 위 그림에서 가장 빨리 끝나는 것은 a1이다.

첫 번째로 a₁을 선택한 뒤 다음으로 빨리 끝나는 것은 a₂다. 그러나 a₁과 시간이 겹치므로 a₂는 제외시킨다. a₃도 a₂와 마찬가지다. 그리고 a₄는 a₁과 겹치지 않으면서 다음으로 빨리끝난다. 이런식으로 선택해나아가다 보면 다음과 같이 된다.

 

 

 

 

 

이렇게 a₁ (1, 4), a₄ (5, 7), a₈ (8, 11), a₁₁ (12, 14) 가 선택되므로 최대 회의 가능한 수는 4가 된다.

이를 토대로 알고리즘을 작성하면 된다. 코드는 크게 어려운 것이 없으니 바로 풀이를 보면서 이해해보도록 하자.

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

크게 어려울 것은 없을 것이다. 이를 큐(Queue)로 풀이하는 방법도 있지만, 일단 기본적인 방법을 익히는 것이 중요하므로 한 개의 알고리즘만 설명하고, Scanner와 BufferedReader로 입력방식에 따른 차이를 확인해보고자 한다.

 

1 . Scanner 

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		
		/*
		  time[][0] 은 시작시점을 의미 
		  time[][1] 은 종료시점을 의미 
		*/
		int[][] time = new int[N][2];
		
		
		for(int i = 0; i < N; i++) {
			time[i][0] = in.nextInt();	// 시작시간 
			time[i][1] = in.nextInt();	// 종료시간 
		}
		
		
		// 끝나는 시간을 기준으로 정렬하기 위해 compare 재정의 
		Arrays.sort(time, new Comparator<int[]>() {
			
			@Override
			public int compare(int[] o1, int[] o2) {
				
				// 종료시간이 같을 경우 시작시간이 빠른순으로 정렬해야한다.  
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				
				return o1[1] - o2[1];
			}

		});
		
		int count = 0;
		int prev_end_time = 0;
		
		for(int i = 0; i < N; i++) {
			
			// 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신 
			if(prev_end_time <= time[i][0]) {
				prev_end_time = time[i][1];
				count++;
			}
		}
		
		System.out.println(count);
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다. 주석으로 모두 설명했으니 크게 어려울 것은 없을 것이다.

 

다만 주의해야 할 점이 있다. 종료시점을 기준으로 오름차순으로 정렬해주되 종료시점이 같을경우 시작시점을 오름차순으로 정렬해주어야 한다.

 

예로들어 다음과 같은 입력이 있다고 가정하자.

8 8
4 8
1 3

 

 

그리고 종료시점으로만 기준으로 정렬하게 된다면 다음과 같이 정렬될 수 있다.

1 3
8 8
4 8

 

 

문제는 여기서 발생한다. 위와같이 정렬되면 (1, 3) 이 선택되고 prev_end_time은 3으로 바뀔 것이다. 그 다음 (8, 8)이 선택되면 prev_end_time은 8로 바뀌어 버린다. 그렇게 되면 (4, 8)은 선택할 수 없게 되는 것이다. 즉, count 값은 2가 되어버리는 것이다.

 

하지만 이는 답이 아니다. 실제로는 (1, 3), (4, 8), (8, 8) 모두 선택되어 count 값은 3이어야 한다. 즉, 위와같은 불상사(?) 혹은 예외를 발생시키는 케이스들을 고려하여 만약 종료시점이 같다면 시작시점을 기준으로 오름차순으로 정렬해주어야 한다.

 

 

 

 

 

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		/*
		  time[][0] 은 시작시점을 의미 
		  time[][1] 은 종료시점을 의미 
		*/
		int[][] time = new int[N][2];
		
		StringTokenizer st;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			time[i][0] = Integer.parseInt(st.nextToken());	// 시작시간 
			time[i][1] = Integer.parseInt(st.nextToken());	// 종료시간 
		}
		
		
		// 끝나는 시간을 기준으로 정렬하기 위해 compare 재정의 
		Arrays.sort(time, new Comparator<int[]>() {
			
			@Override
			public int compare(int[] o1, int[] o2) {
				
				// 종료시간이 같을 경우 시작시간이 빠른순으로 정렬해야한다.  
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				
				return o1[1] - o2[1];
			}

		});
		
		int count = 0;
		int prev_end_time = 0;
		
		for(int i = 0; i < N; i++) {
			
			// 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신 
			if(prev_end_time <= time[i][0]) {
				prev_end_time = time[i][1];
				count++;
			}
		}
		
		System.out.println(count);
	}

}

 

 

 

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 23023515  -  방법 2 : BufferedReader

채점 번호 : 23023505  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

그리디 알고리즘의 대표적인 문제인 활동 선택 문제를 풀어보았다. 물론 그리디 알고리즘이 몇몇 특수한 조건을 만족하거나, 빠르게 최적해를 구하고자 할 경우에 쓰면 좋다.

 

즉, 완벽한 해를 구할 수는 없더라도 그 해에 근접한 값을 도출해내기 위해 쓰인다는 것. 이를 현재까지 포스팅한 단계에서 응용해서 쓴다면 동적계획법을 사용하면서 데이터들을 부분 집합화 하여 그 안에서 그리디알고리즘을 쓰고 연결하는 방식을 생각할 수 있다.

 

혹여 위의 풀이 또는 다른 내용에서 이해가 가지 않은 내용이 있다면 언제든 댓글로 남겨주시면 최대한 빠르게 답변드리겠다.