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

문제 링크:

1931번: 회의실 배정

 

 

난이도: 골드 5

 

 

문제:

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

 

 

입력:

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

 

 

출력:

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

 

 

문제 이해:

문제 이해는 어렵지 않다.

 

회의의 개수와 각 회의의 시작 시간, 끝나는 시간이 주어졌을 때,
회의실을 가장 효율적으로 사용하여 진행할 수 있는 최대 회의 수를 구하는 것이다.

예를 들어, 예제 입력 1의 경우 힌트에 제시된 대로
(1, 4), (5, 7), (8, 11), (12, 14)를 선택하면
회의실을 최대로 활용할 수 있다.

 

 

구현 방향:

작성자는 이 문제만 1시간 30분이 걸렸다.

그리디 알고리즘은 떠올렸지만, 회의시간이 가장 짧은 시간 순서대로 회의실을 배정하면 정답이 나올 것이라 생각했다.

처음에 여러 반례를 따져봤지만 찾지 못했고 이방식으로 진행하여 틀려 오랜 시간을 낭비했다.

 

회의실 사용시간이  가장 짧은 것 부터 선택하면 최적해가 아닌 이유:

바로 다음과 같은 반례가 존재한다.

5
0 3
2 4
3 6
5 7
6 9

정답 3

위 방식으로 이 반례를 입력하면 정답은 (2,4), (5,7)을 선택하여 2가 나온다.

하지만 정답은 (0,3), (3,6), (6,9)로 정답은 3이 된다.

 

결국 이 문제는 회의 총 시간이 짧은 것을 선택하는 것이 아닌,

회의실 사용이 끝나는 시간이 가장 짧은 것을 선택하는 것이 최적해를 보장한다.

 

회의실 사용이 가장 빨리 끝나는 것 부터 선택하면 최적해를 보장하는 이유:

빨리 끝나는 회의를 고르면 뒤에 사용할 여유 구간이 가장 넓게 남는다.

 

따라서 이 방식 그대로 코드로 구현하면 다음과 같다.

 

 

정답 코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static Queue<int[]> q = new PriorityQueue<>(
            (a, b) -> {
                if (a[1] == b[1]) return Integer.compare(a[0], b[0]); // 끝나는 시간 같으면 시작 빠른 순
                return Integer.compare(a[1], b[1]); // 끝나는 시간 기준
            }
    );

    public static int solve(){
        int result=0;
        int[] first = q.peek();
        int lastEnd=first[0];

        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int start=arr[0];
            int end=arr[1];
            //탐색한 마지막 시간이 다음 시작시간보다 작은 경우에만 탐색 가능
            if(lastEnd<=start){
                result++;
                lastEnd=end;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        for(int i=0; i<N; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int start=Integer.parseInt(st.nextToken());
            int end=Integer.parseInt(st.nextToken());
            int time=end-start;
            //q에 시작시간, 끝나는시간, 회의시간 추가
            q.add(new int[]{start,end,time});
        }
        //초기 세팅 끝

        //탐색 시작
        int result = solve();

        //결과 출력
        System.out.println(result);

    }
}

 

주의 사항:

끝나는 시간이 같은 회의가 있으면 먼저 시작되는 시간이 우선순위가 되어야 한다.

예시를 들어보면

3
2 2
1 2
2 3
정답: 3

2 2가 먼저 선택될 경우 (1,2)회의를 진행할 수 없기 때문이다.

 

 

마무리하며:

학부 알고리즘 수업 때 한 번 다뤄봤던 문제였지만,
괜한 고집을 부리느라 예상보다 많은 시간을 쏟았던 문제였다.
이번 경험을 통해, 구현에 앞서 논리와 조건을 충분히 검토한 뒤 시작하는 것이 얼마나 중요한지 다시금 느꼈다.

 

감사합니다.