[Java] 백준(실버-1) 1931번 - 회의실 배정

문제 풀이

---

이 문제는 그리디 알고리즘을 이용하는 대표적인 문제 중 하나이다.

아이디어 도출

이번 문제는 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제다. 즉, 각 회의가 겹치지 않게 최대한 많은 회의를 배정해야 한다.

이와 같이 시간표를 최대한 많이 배정하거나 선택하는 문제를 활동 선택 문제(Activity Selection problem)라고 한다.

잘 생각해보면, 현재 회의의 종룍시간과 다음 회의의 시작시간이 작거나 같으면 회의를 진행할 수 있다고 판단하면 된다. 이렇게 최대한 많은 회의를 배정할 수 있도록 조건을 만족시키기 위해서는 종료시간이 빨라야 한다. 이를 통해, 회의를 종료시간을 기준으로 정렬한 후 위 조건대로 배정해나갸면 된다는 것을 알 수 있다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        int[][] time = new int[N][2];

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i][0] = Integer.parseInt(st.nextToken()); // 시작 시간
            time[i][1] = Integer.parseInt(st.nextToken()); // 종료 시간
        }

        // 종료시간을 기준으로 정렬하기 위한 Comparator 재정의
        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 result = 0;
        int now = 0;

        for(int i=0; i<N; i++) {
            // 회의 종료시간이 다음 회의 시작시간보다 작거나 같으면 회의 진행 가능!
            if(now <= time[i][0]) {
                now = time[i][1];
                result++;
            }
        }

        bw.write(result+"\n");

        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.