C - [백준 1931] 회의실 배정 (feat. 그리디, 퀵 정렬)

2025.02.02 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm)

[자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm)

2025.02.02 - [Computer Science/알고리즘 문제] - C - [백준 2217] 로프 (feat. 그리디, 퀵 정렬)

 

 

 

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

회의실 배정 (백준 1931번) 

문제 설명

한 개의 회의실이 있고, 여러 개의 회의에 대한 시작 시간과 종료 시간이 주어집니다. 겹치지 않게 최대한 많은 회의를 회의실에서 진행할 수 있는 경우의 수를 구하는 문제입니다.

문제 링크: 백준 1931번 회의실 배정

---

Checkpoint

이 문제는 그리디 알고리즘으로 해결할 수 있습니다.

"정렬" 을 잘 활용해야하는 대표적인 문제라고 생각합니다.

평소에 정렬을 해야하고 한다면 정렬 기준을 정하고 기준 값을 오름차순/내림차순을 정해야합니다.

 

해당 문제일 경우 기준값이 될 수 있는 것이 회의 시작시간과 종료 시간이 될 수 있겠습니다.

문제의 요구 사항은 회의의 최대 개수 즉 회의를 최대한 많이 배정했을 때 그 수를 구하는 것으로 정의할 수 있는데

회의를 많이 배정한다 = 회의가 짧게 끝난다.로 생각할 수 있습니다.

즉, 종료 시간이 작을 수록 유리하기 때문에 종료시간을 기준으로 오름차순 정렬을 진행했습니다.

 

// 비교 함수
int compare(const void *a, const void *b) {
    const int *rowA = (const int *)a;
    const int *rowB = (const int *)b;

    // 두번째 열(arry[][1])을 기준으로 정렬
    if (rowA[1] != rowB[1]) {
        return rowA[1] - rowB[1]; // 오름차순
    }

    // 두 번째 값이 같으면 첫 번째 열(arry[][0])을 기준으로 정렬
    return rowA[0] - rowB[0]; // 오름차순
}

 

만약 종료시간이 같을 경우, 시작시간이 작을 수록 일찍 시작하기 때문에 최대값을 뽑아내기 더 적절하다고 판단하여

두 번째 값, 즉 종료시간이 같을 경우 첫번째 열인 시작시간을 기준으로 오름차순 정렬을 진행하였습니다.

 

이는 다음과 같은 상황을 생각해보면 쉽게 이해가 됩니다.

 

1 5

6 9

8 9

 

현재 진행 중인 회의가 1시에 시작하여 5시에 끝납니다.

그 다음 회의를 배정해야하는데 종료시간을 기준으로 정렬해보니 6-9 회의와 7-9가 존재합니다.

시간을 빈틈없이 최대한 활용하기 위해서는 종료시간이 같다는 가정하에 일찍 시작하는 것을 선택해야합니다.(6-9 회의)

그리디 전략

1. 회의를 종료 시간 기준으로 정렬합니다.
2. 정렬된 회의들 중에서 겹치지 않는 회의를 선택합니다.

---

구현 알고리즘

1. 회의 정보를 입력받아 (시작 시간, 종료 시간) 쌍을 저장합니다.
2. 종료 시간을 기준으로 오름차순 정렬합니다.
3. 가장 먼저 끝나는 회의부터 선택하며, 다음 회의가 시작 시간이 현재 회의의 종료 시간 이후일 때만 회의를 선택합니다.
4. 선택된 회의의 개수를 출력합니다.

 

---

구현 코드

/*
https://www.acmicpc.net/problem/1931
C_BOJ_1931_회의실 배정
*/

#include <stdio.h>
#include <stdlib.h>


int conferences[100001][2] = {0};
int N = 0;
int result = 0;

// 비교 함수
int compare(const void *a, const void *b) {
    const int *rowA = (const int *)a;
    const int *rowB = (const int *)b;

    // 두번째 열(arry[][1])을 기준으로 정렬
    if (rowA[1] != rowB[1]) {
        return rowA[1] - rowB[1]; // 오름차순
    }

    // 두 번째 값이 같으면 첫 번째 열(arry[][0])을 기준으로 정렬
    return rowA[0] - rowB[0]; // 오름차순
}

int main() {
    
    scanf("%d", &N);
    for(int i = 0; i < N; i ++){
        scanf("%d %d", &conferences[i][0], &conferences[i][1]);    
    }
    
    qsort(conferences, N, sizeof(conferences[0]), compare);

    // //TESTING SORT
    // printf("Sorted array: \n");
    // for (int i = 0; i < N; i++) {
    //     printf("%d %d \n", conferences[i][0], conferences[i][1]);
    // }

    int current_time = conferences[0][1];
    result ++;

    for(int i = 1; i < N; i ++){
        if(current_time <= conferences[i][0]){
            current_time = conferences[i][1];
            result ++;
        }
    }

    printf("%d",result);
    return 0;
}

 

1) 전역 변수 및 배열 선언

int conferences[100001][2] = {0};
int N = 0;
int result = 0;

• conferences 배열: 회의의 시작 시간과 종료 시간을 저장하는 배열입니다. 최대 100,000개의 회의가 주어질 수 있습니다.
• N: 회의의 개수를 저장하는 변수입니다.
• result: 선택된 회의의 개수를 저장하는 변수입니다.

---

2) 비교 함수

int compare(const void *a, const void *b) {
    const int *rowA = (const int *)a;
    const int *rowB = (const int *)b;

    // 두 번째 열(종료 시간)을 기준으로 정렬
    if (rowA[1] != rowB[1]) {
        return rowA[1] - rowB[1]; // 오름차순
    }

    // 종료 시간이 같으면 시작 시간 기준으로 정렬
    return rowA[0] - rowB[0]; // 오름차순
}

• qsort에서 사용할 비교 함수입니다.
• 회의를 종료 시간 기준으로 오름차순 정렬합니다.
• 만약 종료 시간이 같다면 시작 시간을 기준으로 오름차순 정렬합니다.

---

3) 입력 및 정렬

scanf("%d", &N);
for (int i = 0; i < N; i++) {
    scanf("%d %d", &conferences[i][0], &conferences[i][1]);
}

qsort(conferences, N, sizeof(conferences[0]), compare);

• 회의의 개수 N을 입력받고, 각 회의의 시작 시간과 종료 시간을 conferences 배열에 저장합니다.
• qsort를 사용하여 compare 함수 기준으로 배열을 정렬합니다.

---

4) 회의 선택 로직

int current_time = conferences[0][1];
result++;

for (int i = 1; i < N; i++) {
    if (current_time <= conferences[i][0]) {
        current_time = conferences[i][1];
        result++;
    }
}

• 첫 번째 회의를 선택하고, current_time에 해당 회의의 종료 시간을 저장합니다.
• 이후, 나머지 회의를 순회하며 다음 조건에 따라 회의를 선택합니다.
  • 현재 회의의 시작 시간이 이전 회의의 종료 시간(current_time) 이후인 경우 회의를 선택합니다.
  • 회의를 선택하면 current_time을 현재 회의의 종료 시간으로 갱신하고, result 값을 증가시킵니다.

---

5) 결과 출력

printf("%d", result);

• 최종적으로 선택된 회의의 개수를 출력합니다.

---

3. 예제 입력과 출력

입력 예시

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

출력 예시

4

설명:

• 종료 시간 기준으로 정렬된 회의들 중 선택 가능한 회의는 (1, 4), (5, 7), (8, 11), (12, 14)입니다.
• 따라서 최대 4개의 회의를 진행할 수 있습니다.

---

4. 코드 테스트 및 확인

테스트 케이스 1

3
1 3
2 4
3 5

출력: 2

• 선택 가능한 회의: (1, 3), (3, 5)

테스트 케이스 2

5
0 6
1 4
2 3
3 5
5 7

출력: 3

• 선택 가능한 회의: (2, 3), (3, 5), (5, 7)

---

5. 시간 복잡도

• 입력 크기 N에 대해 정렬이 O(N log N)에 수행됩니다.
• 이후 배열을 순회하면서 회의를 선택하는 과정은 O(N)입니다.
• 따라서 전체 시간 복잡도는 O(N log N)입니다.

---

6. 핵심 요약

• 종료 시간이 빠른 회의부터 선택하는 그리디 알고리즘으로 문제를 해결합니다.
• qsort를 사용하여 종료 시간 기준으로 회의를 정렬한 후, 선택 조건에 따라 회의를 배정합니다.

 

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.