[BOJ] 1931번 회의실배정

개요

그리디 알고리즘으로 풀이하는 문제

문제링크

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Baekjoon1931 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
    
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        for (int t = 0; t < n; t++) {
            st = new StringTokenizer(br.readLine());
            arr[t][0] = Integer.parseInt(st.nextToken());
            arr[t][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, (a,b) -> {
            if (a[1] == b[1])        //종료시간이 같으면 
                return a[0] - b[0]; //시작지점 정렬
            return a[1] - b[1];
        }); //람다함수 형식으로 comparator 전달

        int prevTime = arr[0][1];
        int count = 1;
        for (int i=1;i<n;i++) {
            if(prevTime <= arr[i][0]) { //이전 종료시간이 현재 시작시간보다 작거나 같을 경우
                prevTime = arr[i][1];   //이전 종료시간 업데이트
                count++;    //회의실 배정
            }
        }

        bw.write(count+"\n");
        bw.flush();
    }
}

해결 과정

전형적인 그리디 알고리즘 문제이다. 그리디 알고리즘에서는 문제에 적절한 알고리즘을 찾아서 적용시켜야 하는데 우리는 시간이 겹치지 않게 회의실을 사용할 수 있는 최대 회의의 갯수를 알고 싶은 것이니 규칙을 정해야 한다.

처음에는 시작시간이 작은 순서대로 정렬하고 차례대로 넣어보는 방식을 생각해 보았다.

하지만 이 방법은 중간에 시간이 오래걸리는 회의가 있으면 반례가 생길 수 있고 시간이 겹치지 않는 회의를 찾기엔 최적이 아닌 것 같았다.

다른 방법으로 종료시간을 기준으로 정렬 했을 때를 기준으로 삼았을 경우를 생각해보았고 예제 입력1을 정렬하면 아래그림과 같이 표현된다.

종료시간을 기준으로 정렬하고 종료시간이 같으면 그안에서 시작시간을 기준으로 오름차순 정렬을 해준다. 회의는 동시에 진행할 수 없기 때문에 종료시간을 기준으로 확인해보는 것이 최적의 해라는 것을 알 수 있었다.

결과