[JAVA][Baekjoon] 1931번 회의실 배정 🌟🌟🌟

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

---

📌 접근 방식

1️⃣ 회의실에 최대한 많은 회의를 배정하려면 어떤 기준을 세워야 할까?

• 회의가 겹치지 않게 하려면 현재 회의가 끝난 후에 다음 회의가 시작해야 함
• 따라서, 회의를 배정할 때 현재 시점에서 가장 빨리 끝나는 회의를 선택하면 다음 회의를 시작할 가능성이 높아짐
  → 이를 위해 회의 종료 시간을 기준으로 오름차순 정렬

2️⃣ 정렬 기준을 어떻게 설정해야 할까?

• 기본 정렬 기준: 회의의 종료 시간이 빠른 순서
  → 종료 시간이 빠르면 이후 회의를 배정할 가능성이 높아지기 때문
• 보조 정렬 기준: 종료 시간이 같다면 시작 시간이 빠른 순서
  → 종료 시간이 같은 회의 중에서도 시작 시간이 빠른 회의를 먼저 배정하면 겹치지 않는 회의의 개수를 최대화할 수 있음

3️⃣ 회의를 배정하는 방법은?

• 정렬된 회의 리스트를 순회하며, 현재 회의의 시작 시간이 이전 회의의 종료 시간보다 크거나 같을 때만 그 회의를 배정
  ➡️ 이렇게 하면 회의가 겹치는 경우를 방지할 수 있습니다.
• 회의를 배정할 때마다 종료 시간을 업데이트하고, 회의의 개수를 카운트

---

✅ PASS CODE

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
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 = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int[][] A = new int[N][2]; 

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

        // 종료 시간을 기준으로 오름차순 정렬 (같은 경우 시작 시간을 기준으로 정렬)
        Arrays.sort(A, new Comparator<int[]>() {
            @Override
            public int compare(int[] S, int[] E) {
                if (S[1] == E[1]) {  // 종료 시간이 같으면
                    return S[0] - E[0];  // 시작 시간을 기준으로 오름차순 정렬
                }
                return S[1] - E[1];  // 종료 시간을 기준으로 오름차순 정렬
            }
        });

        // 그리디 알고리즘으로 회의 배정
        int count = 0;  // 최대 배정할 수 있는 회의 수
        int end = -1;   // 이전 회의의 종료 시간 (초기값: -1)

        for (int i = 0; i < N; i++) {
            if (A[i][0] >= end) {  // 현재 회의의 시작 시간이 이전 회의의 종료 시간 이후라면
                end = A[i][1];     // 종료 시간을 업데이트
                count++;           // 회의 배정
            }
        }

        System.out.println(count);
    }
}

 

---

반응형

😊 느낀 점

처음에는 단순히 시작 시간이 빠른 순서로 정렬하면 된다고 생각했다. 하지만 이는 최적의 해를 보장하지 못할 수 있다고 생각되었다. 종료 시간을 기준으로 정렬해야 다음 회의를 더 효율적으로 배정할 수 있다는 것을 깨달았다! 또한, 종료 시간이 같은 경우에는 시작 시간이 빠른 순서로 정렬해야 했기 때문에 정렬 조건을 설정하는 데 조금 어려웠다.

이번 문제를 통해 정렬 기준 설정의 중요성과 그리디 알고리즘의 핵심 원리를 다시 한 번 느낄 수 있었다. 😊