[Java] 백준 #1931 : 회의실 배정

문제분류

그리디 알고리즘
정렬

문제

https://www.acmicpc.net/problem/1931

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

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

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

예제 입력 1

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

예제 출력 1

4

Solution

• 회의 목록의 개수 N, 회의 목록 info를 입력받습니다.

• 이 문제의 핵심은 정렬이라고 생각합니다.
• 최대 회의 수 탐색에 앞서, 회의가 끝나는 시간 기준으로 오름차순 정렬해줍니다. 만약, 끝나는 시간이 동일하다면 시작 시간이 빠른순(오름차순)으로 정렬합니다
• 이때, 정렬 시 compare function으로 람다식을 활용하여 간단하게 표현했습니다.

• info 배열이 정렬된 상태이므로, 배열의 첫 번째 회의보다 빨리 끝나는 회의는 없습니다.
• 첫 번째 회의가 끝나는 시간과 시작 시간이 같거나 가장 가까운 회의가 다음 회의가 됩니다.
• 이때, 시작 시간이 같은 회의가 여러개 존재하더라도, 같을 경우에 대한 오름차순 정렬(시작 시간 기준)을 사전에 해놓았기에, 가장 먼저 등장한 다음 회의가 최선의 경우가 됩니다.

• 조건에 해당하는 회의를 찾을 때마다, cnt를 1씩 증가시켜주고, 다음 회의 탐색을 위해 회의 종료 시간을 갱신해줍니다.
• 모든 회의를 탐색하면(인덱스 N-1까지) cnt를 반환하여 출력합니다.

코드

import java.util.*;

public class Main {
    static int N;            // 회의 목록 개수 저장
    static int[][] info;     // 회의 정보들을 저장한 배열

    // info를 탐색
    public static int search() {
        int cnt = 0;
        int endTime = 0;

        for (int i = 0; i < N; i++) {
            if (endTime <= info[i][0]) {
                endTime = info[i][1];
                cnt++;
            }
        }

        return cnt;
    }

    // main
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력 받기
        N = sc.nextInt();
        info = new int[N][2];

        for (int i = 0; i < N; i++) {
            info[i][0] = sc.nextInt();
            info[i][1] = sc.nextInt();
        }

        // 정렬 (람다식 활용)
        Arrays.sort(info, (o1, o2) -> ((o1[1] == o2[1]) ? o1[0] - o2[0] : o1[1] - o2[1]));
        System.out.println(search());
    }
}

느낀 점

• 시행착오가 있던 문제라 오늘의 치욕을 잊지 않기 위해 기록합니다....

  
  

• 1트 : 입력이 100,000이라 시간제한에 무조건 걸릴 것이라고 예상했지만, 마땅한 방법이 떠오르지 않아 그냥 모든 경우에 대한 완전탐색을 수행했습니다. => 역시나 시간초과

• 2트 : 회의 종료시간 기준 오름차순으로 정렬하여 위와 같은 방법으로 탐색했지만 75~85% 대에서 '틀렸습니다.'가 자꾸 등판... => 실패

• 3트 : compare function이 찝찝해서 봤는데, 혹시나가 역시나 였다.. 회의 종료 시간이 같을 경우 시작 시간도 함께 고려했어야 했는데 그러지 못했었네요..ㅎ compare에 조건문을 추가해주어, 만약 종료시간이 같으면 시작시간 기준 오름차순 정렬을 수행하도록 수정해주었습니다. => Clear

• 람다식을 잘 활용하면 간결하고 강력한 정렬을 수행할 수 있다는 점도 알 수 있었고, 아직은 그리디라는 개념을 정확히는 모르겠지만 대충 이런느낌이겠구나~ 정도 깨달았습니다.