[JAVA] 백준 1931 - 회의실 배정

 

실버 I

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

1931번: 회의실 배정

---

📌 문제

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

---

📤 입력

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

---

📥 출력

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

---

💡 접근방식

회의 시작시간을 기준으로 내림차순으로 정렬하였다.

그리고 시작하자마자 끝나는 회의 또한 고려해야하기 때문에 시작시간이 같은 경우 마감시간이 큰 회의시간을 앞으로 정렬하였다.

예를 들어, 아래와 같이 입력했다고 하면

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

다음과 같이 재정렬된다.

[8, 12]와 [8, 11]은 시작시간이 똑같으므로 마감시간을 비교해 더 큰 [8, 12]가 앞에 오도록 정렬하였다.

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

 

 

그 다음, 현재의 회의 시작시간에서 그 다음 회의 마감시간을 뺀 값이 0보다 크거나 같으면 start를 다음 회의 시간의 시작시간으로 바꿔주고 cnt를 증가시킨다.

위에 정렬된 회의 시간을 예시로 설명을 하자면, start의 초기값이 time[0][0]이므로 start = 12가 된다.

그리고 반복문에 들어가고 현재의 회의 시작시간에서 그 다음 회의 시간마감시간을 뺀 값이 0보다 크거나 같은지 판별한다. 즉, (start - time[1][1])을 뺀게 0보다 크거나 같은지 판별하게 된다. 

여기서 time[1][1]은 12가 된다.  (start - time[1][1]) 은 0이므로 start는 time[1][0]값인 8로 변경되고 cnt가 증가한다.

 

위에서 시작하자마자 끝나는 회의를 고려하여 시작시간이 같은 경우, 끝나는 시간이 더 큰 걸 앞으로 정렬했다고 했는데 예시로 다음과 같이 입력했다고 해보면

4
1 4
4 4
4 4
4 5

 

시작하자마자 끝나는 회의를 고려하지 않고 정렬할 경우 다음과 같이 정렬된다.

4
4 4
4 4
4 5
1 4

그러면 두 번째 회의 시작인 [4, 4]에서 [4, 5]를 건너뛰고 [1, 4]로 넘어가 총 cnt가 3을 출력하게 된다.

하지만 시작하자마자 끝나는 회의시간을 고려해 마감 시간이 더 큰 것을 앞으로 정렬했을 경우 다음과 같이 정렬된다.

4
4 5
4 4
4 4
1 4

그럼 총 cnt가 4를 출력하게 되므로 시작 시간이 같을 때 마감시간이 큰 것을 앞으로 정렬하도록 하였다.

---

💻 코드

package Greedy;

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

public class SLIVER1_BJ1931 {
    /*
        https://www.acmicpc.net/problem/1931
        회의실 배정
     */

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //N입력
        int N = Integer.parseInt(br.readLine());

        int[][] time = new int[N][2];
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            time[i][0] = Integer.parseInt(st.nextToken()); //시작시간
            time[i][1] = Integer.parseInt(st.nextToken()); //끝나는 시간
        }

        //시작시간을 기준으로 내림차순 정렬
        Arrays.sort(time, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                //시작시간이 같은 경우 마감시간이 큰 회의시간을 앞에 배치
                if(o2[0] == o1[0])
                    return o2[1]-o1[1];

                return o2[0]-o1[0];
            }
        });

        int start = time[0][0];
        int cnt = 1;

        for(int i = 1; i < N; i++) {
            if ((start - time[i][1]) >= 0) {
                start = time[i][0];
                cnt++;
            }
        }

        //결과출력
        System.out.print(cnt);
    }

}

---

📝 NOTE

처음에 메모리초과 오류가 났었다. 그 이유는 time변수를 선언할 때 메모리 선언을 int[][] time = new int[N][N]; 이라고 선언했었다. 따라서 int[][] time = new int[N][2];로 다시 선언하여 메모리초과 오류를 해결하였다.

배열을 선언할 때 크기 선언을 잘 해줘야겠다.

 

- 참고

https://www.acmicpc.net/board/view/122182

글 읽기 - 막히시는 분들 보세요(스포주의)