[백준 11000] 강의실 배정

 

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

11000번: 강의실 배정

 

정답 소스코드는 제일 밑에 있음!

시간 초과로 고생했던 문제...

 

 

---

첫 번째 시도

처음 생각은 벡터에 넣어서 그리디 방식으로 직접 삭제시키며 방을 만들어갔다.

결과는 시간 초과.

 

 
typedef pair<int, int> P;
 
int n;
vector<P> lec;
vector<bool> isDeleted;
int rooms;
 
int findFirstNotDeleted(){
    int i = 0;
    for(i = 0; i < n; i++){
        if(isDeleted[i] == false)
            return i;
    }
    return i;
}
 
// 시간초과
void solve(){
    while(1){
        int firstIndex = findFirstNotDeleted();
        if(firstIndex == n)
            break;
 
        int endtime = lec[firstIndex].second; // 제일 처음 마치는 시간.
        //lec.erase(lec.begin());
        isDeleted[firstIndex] = true;
 
        for(int i = 0; i < lec.size(); i++){
            // 시작 가능한 가장 빠른 강의 찾기
            if(endtime <= lec[i].first && !isDeleted[i]){
                endtime = lec[i].second;
                isDeleted[i] = true;
                //lec.erase(lec.begin()+i);
                //i--;
            }
        }
        rooms++;
    }
}
 
 
 
 

 

---

두 번째 시도

두 번째로 끝나는 시간을 벡터에 넣어가면서 시도해보았다.

즉 벡터에 들어간 시간은 각 방의 끝나는 시간. 

하지만 이 역시도 각 방을 다 돌면서 가능한 빠른 시간을 찾아야 했기에 시간 초과.

 

 
vector<int> roomsEndTime;
void solve2(){
    int i = 1, j = 0 ;
    roomsEndTime.push_back(lec[0].second);
    for(i = 1; i < n; i++){
        for(j = 0; j < roomsEndTime.size(); j++){
            // 이어서 강의 가능한 강의실에 추가.
            if(lec[i].first >= roomsEndTime[j]){
                roomsEndTime[j] = lec[i].second;
                break;
            }
        }
        // 알맞은 강의실 없으면 새로 판다.
        if(j == roomsEndTime.size()){
            roomsEndTime.push_back(lec[i].second);
        }
    }
}
 
 

---

마지막 시도 (정답)

결국 해답을 얻을 수 있었던 자료구조는.... 바로 "Priority Queue" 였다.

두 번째 방법에서의 큰 오류는 가장 빠른 시간만을 찾기위해 벡터의 모든 크기를 다 탐색했던 것..

바로 가장 빠른 시간만을 반환해주는 우선순위 큐를 사용하면 훨씬 더 빠른 시간안에 풀 수 있었다.

 

 
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;
 
typedef pair<int, int> P;
 
int n;
vector<P> lec;
 
// 각 방이 끝나는 시간을 넣어둠.
// 탐욕스러운 방식으로 진행하기 위해 가장 빨리 끝나있는 방(우선순위 큐의 탑)에 넣음.
// 가장 빨리 끝나는 방에도 못넣으면 새로 방 파기.
priority_queue<int, vector<int>, greater<int>> fastestRoomsTime;
void solve3(){
    fastestRoomsTime.push(lec[0].second);
    for(int i = 1; i < n; i++){
        // 가장 빠르게 이용가능한 방에 들어갈 수 있음.
        if(fastestRoomsTime.top() <= lec[i].first){
            // 이용한 방의 끝나는 시간을 바꿔줌.
            fastestRoomsTime.pop();
            fastestRoomsTime.push(lec[i].second);
        }else{ // 이용 불가하면 새로운 방 파기.
            fastestRoomsTime.push(lec[i].second);
        }
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    lec.resize(n);
    
    for(int i = 0; i < n; i++)
        cin >> lec[i].first >> lec[i].second;
    sort(lec.begin(), lec.end());
 
    solve3();
    cout << fastestRoomsTime.size() << '\n';
    return 0;
}
 
 

 

결과는 성공! 

진짜 자료구조 공부 좀 해야겠다.. (질문게시판에 글 감사합니다~~)