1 분 소요

[공지사항] 알고리즘 카테고리 포스트 살펴보기

:rocket: 문제 설명

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

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

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



:rocket: 문제 풀이

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




public 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));
        StringTokenizer st;
        int meetingNum = Integer.parseInt(br.readLine());

        ArrayList<int[]> meetingList = new ArrayList<>();

        for (int i = 0; i < meetingNum; i++){
            st = new StringTokenizer(br.readLine());
            int[] meeting = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            meetingList.add(meeting);
        }

        // 풀이
        Collections.sort(meetingList, (o1, o2) -> {
            if (o1[1] == o2[1])
                return o1[0] - o2[0];
            return o1[1] - o2[1];
        });

        int availableMeetingCount = 0;
        int currentTime = 0;
        for (int i = 0; i < meetingNum; i++){
            if (currentTime <= meetingList.get(i)[0]){
                availableMeetingCount++;
                currentTime = meetingList.get(i)[1];
            }
        }
        bw.write(Integer.toString(availableMeetingCount));
        bw.flush();
    }
}

그리디 알고리즘으로 풀었다.

각 회의의 시작시간과 끝시간을 담은 int[] 배열을 ArrayList에 담은 후,

해당 ArrayList를 회의가 끝나는 시간을 기준으로 오름차순 정렬했다.

같은 시간대에 끝나는 회의는 회의 시작 시간을 기준으로 정렬시켰다. (사실 이 부분은 이 문제에서 별로 중요한 것 같지는 않기는 하다.)

이렇게 한 이유는 이제 0시부터 회의를 채워넣을 건데, 회의가 끝나는 시간이 빠른 회의를 먼저 넣어야 다음 회의를 넣을 수 있는 시간 범위가 늘어나기 때문이다.

즉, 이렇게 해야 다음 회의가 더 빨리 시작하도록 (촘촘히) 회의를 채워넣을 수 있다.


그리디 알고리즘에서 말한대로 현재 회의를 채워넣는 것이 다음 회의를 선택하는데 영향이 없고, 지금 당장 넣을 수 있는 (빠르게 끝나는) 회의를 집어 넣는 것이 전체 문제의 해답(최적해)로 이어진다.

아주 적합한 그리디의 예시라고 볼 수 있다.

참고