[BOJ G5][C++] 백준 11000번: 강의실 배정 (시간초과)

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

11000번: 강의실 배정

 

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

 

풀이

4%에서 틀렸습니다 가 뜬다면

강의를 알맞게 정렬했는지 확인해보자
끝나는시간이 빠른 순으로 하면 안된다. 강의시간(끝-시작)이 짧을수록 먼저 배정해야한다

본 문제에서는 {시작시간, 끝나는시간} 을 pair 자료형을 이용하여 sort를 해주어 한번에 정렬했다

 

시간초과 가 뜬다면

본 문제의 입력이 매우 많으므로 O(n^2) 의 시간복잡도로는 풀이가 불가능하다는 점을 참고하자 (아래아래 시행착오 참고)

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int, int> p;  // {시작시간, 끝나는시간}

int solution(int n, vector<p> &lecture) {
    priority_queue<int, vector<int>, greater<int>> room; // room.top() = 사용중인 강의실중 가장 빨리 끝나는 강의실의 끝나는 시간
    
    sort(lecture.begin(), lecture.end()); // 시작시간이 빠른 순서대로 정렬 (시작시간이 같다면 끝나는 시간이 빠른 순서)
    
    for(int i=0; i<n; i++) {
        if(!room.empty() && room.top() <= lecture[i].first)
            // 가장 빨리 끝날 강의실의 사용이 가능하다면 해당 강의실에 강의 배정
            room.pop();
        
        room.push(lecture[i].second);  // 가장 빨리 끝날 강의실의 사용이 불가능하다면 새 강의실에 강의 배정
    }
    
    return room.size();
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin >> n;
    vector<p> lecture(n, {0,0});
    for(int i=0; i<n; i++)
        cin >> lecture[i].first >> lecture[i].second;
    
    cout << solution(n,lecture);

    return 0;
}

/*
 */

 

시행착오

처음에는 편하게 구현했으나 강의실을 배정하는 과정에서 이중 for문을 돌려 시간복잡도가 O(n^2)가 되었고,

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> p;  // {시작시간, 끝나는시간}

int solution(int n, vector<p> &lecture) {
    vector<int> room(n,0); // room[i] = i번 강의실의 마지막 수업이 끝난 시간, 강의실의 최대 개수는 n을 넘지 않음
    
    sort(lecture.begin(), lecture.end()); // 시작시간이 빠른 순서대로 정렬
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            // 강의실 사용이 가능하다면(강의실끝나는시간 <= 강의시작시간) 강의 배정
            if(room[j] <= lecture[i].first) {
                room[j] = lecture[i].second;
                break;
            }
        }
    }

    int maxRoom=0;
    for(int i=0; i<n; i++) // 강의가 배정된(room[i]가 0이 아닌) 강의실의 수 카운트
        if(room[i]>0)
            maxRoom++;
    return maxRoom;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin >> n;
    vector<p> lecture(n, {0,0});
    for(int i=0; i<n; i++)
        cin >> lecture[i].first >> lecture[i].second;
    
    cout << solution(n,lecture);

    return 0;
}

/*
 */

시간 조건이 까다로운 본 문제 특성상 바로 시간초과가 떴다..

강의실에 해당하는 부분을 우선순위큐 (priority_queue, 힙(heap)) 를 이용하여 구현하고 시간복잡도를 낮춰서 성공했다.