문제 출처

단계별로 풀어보기 > 그리디 알고리즘 > 회의실 배정
https://www.acmicpc.net/problem/1931

문제 설명

한 개의 회의실을 N개의 회의가 사용하려고 한다.
각 회의는 시작, 끝 시간이 주어질 때, 회의가 겹치지 않게 가장 많이 회의실을 이용할 수 있는 횟수를 return하라.

접근 방법

회의 시간을 2차원 배열로 생성한 뒤, 종료 시간에 대해 오름차순으로 정렬한다. 단, 종료 시간이 같은 경우에는 시작 시간을 오름차순 기준으로 정렬한다.

정렬한 2차원 배열을 순회하면서, 회의가 마지막으로 끝난 시간과 다음 회의의 시작 시간을 비교하며 만약 회의 시작시간이 이 전 회의의 종료시간과 같거나 크다면 해당 회의의 종료시간을 마지막으로 끝난 시간으로 정한다. 조건에 맞을 때마다 count를 1증가 시킨다.

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

public class 회의실_배정 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int meeting[][] = new int[N][2];

        StringTokenizer st;

        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<2; j++){
                meeting[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Arrays.sort(meeting,(o1,o2) -> {
            if(o1[1] == o2[1]) return o1[0]-o2[0];
            return o1[1] - o2[1];
        });


        int lastFinishedTime = 0;
        int count = 0;

        for(int i = 0; i<N; i++){
            if(lastFinishedTime <= meeting[i][0]){
                count++;
                lastFinishedTime = meeting[i][1];
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();
    }
}

Review

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

public class 회의실_배정_review {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int [][] meeting = new int[N][2];

        StringTokenizer st;
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<2; j++){
                meeting[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Arrays.sort(meeting, (o1, o2) -> {
            if(o1[1] == o2[1]) return o1[0] - o2[0];
            return o1[1] - o2[1];
        });

        int lastFinishedTime = 0;
        int count = 0;

        for(int[] k : meeting){
            if(lastFinishedTime <= k[0]){
                count++;
                lastFinishedTime = k[1];
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음 헷깔린 부분은 종료시간에 대해서만 정렬을 하면 되지 않을까? 였었다. 종료시간이 같은 경우 시작 시간에 대해서 정렬하지 않으면, 해당 문제는 틀린다.
예를 들어
(0,3), (11, 11), (7, 11) 가 주어지면 시작 시간을 기준으로 오름차순 정렬 조건이 없으면
(0,3), (11, 11) 만 수행된다.
하지만 시작 시간을 기준으로 오름차순 정렬 조건이 있다면
(0,3), (7, 11), (11, 11) 이 수행되어 올바른 계산을 할 수 있다.

문제푼 흔적

Review