[백준, 1931번] 회의실 배정 (그리디 알고리즘 greedy, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 회의실 배정"문제는 회의 시작 시간과 종료 시간이 공백을 기준으로 입력이 되고, 겹치지 않는 최대 회의의 수를 구하는 문제입니다.

public class BOJ1931 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        boolean[] timeline = new boolean[100001]; // 시간 범위를 추적하기 위한 배열
        int count = 0;


        for (int i = 0; i < N; i++) {
            StringTokenizer token = new StringTokenizer(br.readLine());
            int start_time = Integer.parseInt(token.nextToken()); // 회의 시작시간
            int end_time = Integer.parseInt(token.nextToken()); // 회의 종료시간

            boolean isOverlap = false;

            for (int j = start_time; j <  end_time; j++) {
                if(timeline[j]){
                    isOverlap = true;
                    break;
                }
            }

            if(!isOverlap){
                for (int j = start_time; j < end_time ; j++) {
                    timeline[j] = true;
                }
                System.out.println(start_time + " " + end_time);
                count++;
            }
        }
        System.out.println(count);
    }
}

 

처음에는 위와 같이 풀이했습니다. 출력은 맞지만 회의실 배정 문제의 기본 조건을 완전히 충족하지 못하기 때문에 틀리는 풀이입니다.

 

문제의 핵심 

 

• 정렬 필요성
  • 입력된 회의는 시작 시간과 종료 시간 기준으로 정렬 후 처리해야 최적의 결과를 얻을 수 있습니다.
  • 종료 시간이 빠른 회의를 우선적으로 배정해야 더 많은 회의를 배정할 수 있습니다.
• 현재 코드는 정렬을 고려하지 않음
  • 입력된 순서대로 처리하기 때문에 최적의 결과를 보장하지 않습니다.

 

예제 입력1번을 보면 종료시간이 오름차순으로 정렬되어있지만, 문제에서는 정렬이 보장되어있다는 말이 없습니다. 따라서 더 많은 회의실을 배정하려면 정렬이 필수입니다.

 

여기서 알 수 있듯이 "종료 시간이 빠른 회의를 먼저 선택"하는 것이 최적의 결과를 보장합니다. 따라서 그리디 알고리즘을 사용한다면 효율적으로 풀이할 수 있습니다.

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기

---

정렬을 하지 않으면, 입력 순서대로 회의를 처리하기 때문에 최적의 해를 보장하지 못합니다. 아래 예시를 통해 살펴보겠습니다.

 

 

ex1 )

5
1 4
2 3
3 5
0 6
5 7

 

정렬하지 않고 입력 순서대로 처리

1. 첫 번째 회의 (1, 4)을 선택
2. 두 번째 회의 (2, 3)은 (1, 4)와 겹치므로 선택하지 않음
3. 세 번째 회의 (3, 5)은 (1, 4)와 겹치므로 선택하지 않음
4. 네 번째 회의 (0, 6)은 첫 번째 회의 (1, 4)와 겹치므로 선택하지 않음
5. 다섯 번째 회의 (5, 7)은 (1, 4), (3, 5), (0, 6)과 겹치지 않으므로 선택

선택된 회의: (1, 4), (5, 7) → 총 2회의 회의가 선택됨.

 

 

종료 시간 기준 정렬

5
1 4
2 3
3 5
0 6
5 7

-----

2 3
1 4
3 5
0 6
5 7

• 첫 번째 회의 (2, 3)을 선택
• 두 번째 회의 (1, 4)은 (2, 3)과 겹치므로 선택하지 않음
• 세 번째 회의 (3, 5)은 (2, 3)과 겹치지 않으므로 선택
• 네 번째 회의 (0, 6)은 (3, 5)와 겹치므로 선택하지 않음
• 다섯 번째 회의 (5, 7)은 (3, 5)와 겹치지 않으므로 선택

선택된 회의: (2, 3), (3, 5), (5, 7) → 총 3회의 회의가 선택됨.

---

따라서, 회의들이 정렬되지 않은 상태에서 선택을 진행하면 최적의 해를 구할 수 없으며, 그리디 알고리즘을 적용하기 위해서는 종료 시간 기준으로 회의를 정렬한 후에 선택하는 것이 중요합니다.

 

정렬을 하지 않았을 때는 더 적은 회의가 선택되는 이유는, 회의의 종료 시간을 고려하여 가능한 한 많은 회의를 선택하는 전략이 필요하기 때문입니다.

 

회의를 선택할 때, "가장 먼저 끝나는 회의"를 선택해야 더 많은 회의를 배정할 수 있습니다.

 

전체 코드

 

먼저 빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아줍니다. 그리고, 회의 시작시간과 종료시간이 공백을 기준으로 입력되기 때문에 StringTokenizer 클래스를 사용하여 공백을 기준으로 토큰으로 분리해줍니다.

 

회의의 수가 N만큼 입력되기 때문에 [N][2]의 크기를 가진 배열을 초기화해줍니다. 이 때 2로 초기화 하는 이유는 시작 시간과 종료시간을 받기 위함입니다.

 

그리고 회의 시간을 초기화해주고, 문제의 핵심인 정렬을 해줍니다.

 

종료 시간이 빠른 회의를 먼저 선택해야 가능한 많은 회의실을 배정할 수 있습니다. 따라서 회의들을 종료 시간 기준으로 오름차순 정렬하고, 종료 시간이 같을 경우 시작 시간을 기준으로 오름차순 정렬합니다.

 

이렇게 정렬된 회의 시간을 저장한 배열 meetings에서, meetings를 순회하며 회의 시작 시간이 이전 회의의 종료 시간보다 크거나 같을 경우 회의실 배정 카운트를 증가시키고, 종료 시간을 업데이트합니다.

 

예를 들어 설명하자면,

문제의 예제 1번대로 입력이 주어진다면 먼저 1 4는 처음이니깐 회의실 배정이 가능합니다.

• 3 5
  • [3,5]일 경우 시작시간인 3이 배정된 [1,4]의 종료시간 4보다 작기 때문에 겹치게 됩니다.
• [0,6]
  • [0,6]일 경우 시작시간인 0이 배정된 [1,4]의 종료시간 4보다 작기 때문에 겹치게 됩니다.
• [5,7]
  • [5,7]일 경우 시작시간인 5가 배정된 [1,4]의 종료시간 4보다 크기때문에 겹치지 않습니다.