[백준 11000] 강의실 배정(C++)

📕문제

---

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

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

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

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

📕입력

---

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

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

📕출력

---

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

 

🔎문제 해석

나는 처음에  pair 형태(수업 시작 시간, 수업 끝나는 시간)로 선언하고 , 수업 시작 시간을 기준으로 오름차순으로 정렬되게끔 하는 prority_queue를 선언하고, 일차원 벡터를 통해서 강의실을 구성했다.

 

그렇게 하니 ----> 시간초과.

아마도 코드에서 pq를 굉장히 많이 넣었다 뺏는데 그때 pair형태여서, 시간 초과가 일어난것 같았다.

그래서 나는 pair를 인자로 가지는 vector로 수업 시작시간, 수업 종료 시간을 넣어줬고, prority_queue를 이용해서 강의실에서 수업을 하고 있는 종료 시간을 넣어주었다.

 

그렇게 하니 시간초과가 해소되고 문제가 해결되었다.

 

우선 풀이 방식은 굉장히 쉽게 도출했다.  이러한 강의실 배정 같은 문제는 그리디 알고리즘의 대표적인 예로 너무 자주 풀어봤던 알고리즘이라 쉽게 해결할 수 있었다. [시간 초과는 몰랐지만..]

 

예를 들어서 설명해보겠다.

1	3
2	4
3	5

입력받은 수업의 시간들은 오름차순이 보장되어 있지 않기 때문에 코드에서 오름차순으로 정렬해줘야 한다.

 

우선 첫 강의실에는 당연히 (1,3)에 해당하는 수업이 배정되어야 할 것이다.

그럼 이제 다음 수업인 (2,4)는 (1,3) 수업이 사용하고 있는 강의실을 사용하지 못한다.

왜냐하면 (1,3)은 3에 수업이 끝나지만, (2,4)는 2에 수업이 시작되어야 하기 때문에 새로운 강의실을 배정해줘야 한다.

그럼 이제 우리는 강의실을 2개 사용하고 있고. 강의실_1 = 3, 강의실_2 = 4에 수업이 종료한다는 사실을 알고 있어야 한다.

그다음 수업인 (3,5)에 시작시간과  현재 사용 중인 강의실_1과 강의실_2에 종료시간과 비교해서 만약

시작시간이 강의실_1과 2에 종료시간보다 크면 강의실_1과 강의실_2를 사용할 수 있다.

작다면 새로운 강의실을 배정받아야 한다.

이제 이걸 일반화시켜보면 (시작시간, 끝나는 시간)에서 s는 강의실_N의 종료시간과 비교해준다.

만약 시작시간이 강의실_N에 종료시간보다 작다면 강의실 N을 사용할 수 없기에, 새로운 강의실을 배정받아야 한다.

처음에 나는 모든 강의실과 비교를 했었다. --> 시간 초과 [그렇다면 비교의 횟수를 줄여야 한다 --> prority_Queue 사용

그래서 나는 강의실_N에 값을 prority_Queue에 넣어서 항상 오름차순으로 정렬되게끔 했고,

강의실_top()에 해당하는 시간에만 비교 후[뒤의 강의실은 종료시간이 무조건 크기 때문] 함수를 처리했다.

 

💻코드

/*
백준 11000 골드5 강의실 배정
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>>pq; //강의실에서 수업이 끝나는 시간을 오름차순으로 저장.
vector<pair<int, int>>Time; //시작 시간과 끝나는 시간을 저장하는 배열
int main()
{
    cin >> n; // n개의 수업
    for (int i = 0; i < n; i++)
    {
        int start, finish;
        cin >> start >> finish;
        Time.push_back(make_pair(start, finish));
    }
    sort(Time.begin(), Time.end()); //시작시간과 끝나는 시간중에서 시작시간을 기준으로 오름차순 정렬
    pq.push(Time[0].second); //가장 먼저 시작되는 수업을 일단 강의실에 배정함.
    
    for (int i = 1; i < Time.size(); i++) {
        bool flag = true;
        if (pq.top() <= Time[i].first) { //제일 빨리 끝나는 강의실이 해당 수업보다 일찍 끝난다면 바로 강의실 배정해줌.
            //기존 강의실을 배정핻줌.
            pq.pop();
            pq.push(Time[i].second);
            flag = false;
        }
        if (flag == true) { //만약 제일 빨리 끝나는 강의실이 수업시작 시간보다 늦다면 새로운 강의실을 배정해줌.
            pq.push(Time[i].second);
        }
    }
    cout << pq.size();
}

 

✔느낀 점

• 전형적인 그리디 문제였다.
• 이번 문제를 풀면서 알고리즘 적으로 문제가 아닌 내가 사용한 자료구조 때문에 시간 초과가 날 수 있다는 사실을 깨닫게 되었다.
• 이제 문제를 풀면서 적절한 자료구조를 사용해야겠다고 느꼈다.