C - [시간초과 백준 11000] 강의실 배정 (feat. 우선순위 큐 미학습

 

 

그리디 알고리즘 학습 중 풀게된 문제입니다.

 

그리디 알고리즘 방법으로 수업을 퀵 정렬 한 후 카운팅을 진행하였으나 시간 초가 발생

 

• 현재 코드는 O(N²) 시간 복잡도를 가집니다.
  각 강의에 대해 중첩 루프를 사용해 배정할 강의를 찾고 있기 때문입니다.
• N이 최대 200,000일 수 있으므로 시간 초과가 발생할 가능성이 높습니다.

 

문제 분류를 보니 우선순위 큐가 언급되어 있는 것을 보아 우선순위 큐를 학습하여 해당 코드를 새롭게 접근할 필요성이 있다고 생각이 듭니다.

 

하단은 시간초과가 난 코드입니다.

 

/*
C_BOJ_11000_강의실 배정
https://www.acmicpc.net/problem/11000
*/

#include <stdio.h>
#include <stdlib.h>
#define MAX 200000

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

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

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


int main() {
    int N = 0;
    int arry[MAX][2];
    int visited[MAX];
    
    int result = 0;
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        scanf("%d", &arry[i][0]);
        scanf("%d", &arry[i][1]);
    }

    qsort(arry, N, sizeof(int) * 2,compare);
    // for(int i = 0; i < N; i ++){
    //     printf("%d % d\n", arry[i][0], arry[i][1]);
    // }

    for(int j = 0; j < N; j ++){
        if(visited[j] == 0){
            visited[j] = 1;
            result ++;
            int current[2] = {arry[j][0], arry[j][1]};
            for(int i = j+1; i < N; i ++){
                if(arry[i][0] >= current[1]){
                    current[0] = arry[i][0];
                    current[1] = arry[i][1];
                    visited[i]=1;
                }
            }
        }
    }

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