[백준/JAVA] 1931번: 회의실 배정

 

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

 

- 정답 코드

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

// 회의실을 사용할 수 있는 회의의 최대 개수
// (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 11


        // 시작시간, 끝나는 시간 입력받음
        int[][] meetings = new int[N][2];

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

        // 끝나는 시간 기준 정렬
        Arrays.sort(meetings, (a, b) -> {
            // 끝나는 시간이 같으면 시작 시간 기준 정렬
            if(a[1] == b[1]) {
                return a[0] - b[0];
            }else{
                return a[1] - b[1];
            }
        });

        int count = 0; // 회의 최대 개수
        int endTime = 0; // 현재 회의 끝나는 시간

        // 회의 선택
        for(int i = 0; i < N; i++) {
            // 현재 회의 시작 시간이 이전 회의 끝나는 시간 이후라면
            if(meetings[i][0] >= endTime) {
                // 현재 회의 끝나는 시간을 업데이트
                endTime = meetings[i][1];
                count++;
            }
        }

        System.out.println(count);
    }
}

 

---

- 문제 풀이 

1. 회의 시작 시간과 끝나는 시간 입력받기

  int[][] meetings = new int[N][2]; // 회의의 시작 시간과 끝나는 시간을 저장할 배열
        
        // 시작 시간과 끝나는 시간을 입력받음
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            meetings[i][0] = Integer.parseInt(st.nextToken()); // 시작 시간
            meetings[i][1] = Integer.parseInt(st.nextToken()); // 끝나는 시간
        }

 

- 결과 : [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

 

2. 끝나는 시간을 기준으로 회의를 정렬

        // 끝나는 시간을 기준으로 정렬, 끝나는 시간이 같으면 시작 시간을 기준으로 정렬
        Arrays.sort(meetings, (a, b) -> {
            if (a[1] == b[1]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });

- 끝나는 시간이 같을 경우 시작 시간을 기준으로 정렬합니다. (오름차순)

- 정렬 후 : [[1, 4], [3, 5], [5, 7], [8, 11], [12, 14], [0, 6], [3, 8], [5, 9], [6, 10], [8, 12], [2, 13]])

 

3. 정렬된 회의를 순서대로 선택하여 최대 회의 개수를 계산

        int count = 0; // 사용할 수 있는 회의의 최대 개수
        int endTime = 0; // 현재 회의가 끝나는 시간
        
        // 회의를 선택
        for (int i = 0; i < N; i++) {
            if (meetings[i][0] >= endTime) { // 현재 회의의 시작 시간이 이전 회의의 끝나는 시간 이후라면
                endTime = meetings[i][1]; // 현재 회의의 끝나는 시간을 업데이트
                count++; // 회의 개수 증가
            }
        }
        
        System.out.println(count); // 최대 사용할 수 있는 회의의 최대 개수 출력
    }
}

 

- 각 회의를 순서대로 검사하여, 현재 회의의 시작 시간이 endTime보다 크거나 같으면 회의를 선택하고 endTime을 업데이트합니다.

 

회의 선택 과정:

1. 회의1 (1, 4):
   • meetings[0][0] (1) >= endTime (0) 조건이 참입니다.
   • endTime을 4로 업데이트합니다.
   • count를 1로 증가시킵니다.
2. 회의2 (3, 5):
   • meetings[1][0] (3) < endTime (4) 조건이 거짓입니다.
   • 회의를 선택하지 않습니다.
3. 회의3 (5, 7):
   • meetings[2][0] (5) >= endTime (4) 조건이 참입니다.
   • endTime을 7로 업데이트합니다.
   • count를 2로 증가시킵니다.
4. 회의4 (8, 11):
   • meetings[3][0] (8) >= endTime (7) 조건이 참입니다.
   • endTime을 11로 업데이트합니다.
   • count를 3로 증가시킵니다.
5. 회의5 (12, 14):
   • meetings[4][0] (12) >= endTime (11) 조건이 참입니다.
   • endTime을 14로 업데이트합니다.
   • count를 4로 증가시킵니다.
6. 나머지 회의들은 조건을 만족하지 않아 선택되지 않습니다.

 

- 회의를 선택한 결과:

• 회의1: (1, 4)
• 회의4: (5, 7)
• 회의8: (8, 11)
• 회의11: (12, 14)