백준 알고리즘 1931번: 회의실 배정

문제 정보

---

 

1931번: 회의실 배정

 

 

핵심

---

최적의 해를 찾는 과정을 잘 생각해야 하는 문제인것 같다고 생각했고, 해당 문제를 풀이하는 과정은 다음과 같다

먼저 해당 회의시간(시작시간, 종료시간) 을 종료시간을 기준으로 정렬시킨다

왜냐하면, 현재 위치를 기준으로 가능한 회의 중 종료시간이 가장 빠른(작은) 회의를 선택해야 더 많은 회의를 진행할 수 있기 때문이다

 

1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

위는 예제의 데이터인데, 이미 정렬되어 있지만 정렬한다면 위와 같은 순서로 정렬될 것이다

 

만약 종료 시간이 같다면? 시작 시간이 작은(빠른) 회의를 기준으로 정렬해 주어야 한다(두 번째 정렬 조건)

왜냐하면, 다음과 같은 엣지 케이스가 있을 수 있기 때문이다

1 2
5 5
3 5

이 경우에 1에 시작한 회의는 2 전에 끝나고, 5에 시작한 회의는 5 전에 끝난다

그 후로, 3에 회의를 시작할 수 없게 되므로 위 경우에는 2개의 회의가 진행되게 된다

 

하지만, 회의의 종료 시간에 회의가 시작할 수 있기 때문에 만약 위처럼 정렬되는 것이 아닌,

1 2
3 5
5 5

이처럼 정렬된다면, 3에 시작한 회의가 5 전에 끝나게 되고 5에 회의 하나를 더 시작할 수 있게 된다

 

위 설명에서 알수 있듯 우리는 이전 회의가 끝난 시간(meetingEndTime) 을 기록해 두고

해당 시간(이전 회의가 끝난 시간)보다 다음 회의의 시작 시간이 크거나 같다면 가능한 회의라고 보고,

다음 회의의 끝난 시간을 다시 meetingEndTime 으로 설정하고 반복을 진행하면 된다

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[][] meeting = new int[n][2];
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            meeting[i][0] = Integer.parseInt(st.nextToken());
            meeting[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(meeting, (o1, o2) -> o1[1]!=o2[1] ? o1[1]-o2[1] : o1[0]-o2[0]);

        int meetingEndTime = 0;
        int count = 0;
        for(int i=0; i<n; i++) {
            if(meeting[i][0] >= meetingEndTime) {
                meetingEndTime = meeting[i][1];
                count++;
            }
        }
        System.out.println(count);
    }
}

Arrays.sort() 를 통해 위에서 언급했던 2차원 배열의 정렬을 수행할 수 있으며

정렬 기준은 lambda 식으로 작성하였으며 (Comparator)

 

o1[1] != o2[1] (두 회의의 끝나는 시간이 다르다면)

o1[1]-o2[1] (회의의 끝나는 시간을 기준으로 오름차순 정렬)

 

두 회의의 끝나는 시간이 같다면 o1[0] - o2[0] (회의가 시작하는 시간을 기준으로 오름차순 정렬) 을 실시하면 된다

 

Reference

---

[Java] 2차원 배열 정렬 (오름차순, 내림차순, 다중 조건)

 

[ JAVA ] Arrays.sort()의 내부 동작(1)

 

Source Code on GitHub

---