[TIL] 24.03.08 알고리즘

1. 알고리즘 문제 해결

 

 

최소 회의실 개수(백준 19598):

 어제 풀었던 것과 마찬가지로 우선순위 큐를 이용하는 문제다. 회의 배열의 크기와 주어질 수 있는 시간의 최대값이 충분히 작다면 배열 하나와 브루트 포스를 이용할 수도 있겠지만, 이 문제는 그러기엔 큰 수들이 주어질 수 있다.

 

 

 사실 시간 진행에 따라 회의들의 타임 테이블을 나란히 두고 생각해보면 모든 시간에 대해 회의실 수를 따져볼 필요는 없음을 알 수 있다. 모든 회의들을 탐색하면서, 회의가 시작하는 시점에 필요한 회의실 수만 따져줘도 충분하다.

 특정 회의가 시작되는 시점을 기준으로 필요 회의실 수를 계산하려면, 진행되려고 하는 회의의 시작 시간보다 끝나는 시간이 빠른 회의들을 진행 중인 회의 목록에서 제거하고, 남은 회의들의 수를 세면 될 것이다. 그리고 이 과정은 우선순위 큐를 이용해 구현했을 때, O(log n)만에 실행될 수 있다.

 하지만 여기까지만 생각하면, 다음으로 탐색하는 회의가 현재 탐색중인 회의보다 일찍 시작되고 일찍 끝나는 경우를 따질 수 없을 것이다. 이를 해결하기 위해, 회의 목록을 시작 순서가 빠른 순으로 정렬해두고 그 순서대로 탐색을 진행해야 한다. 그렇게 되면 놓치는 것 없이 우선순위 큐를 이용해 특정 회의 시작 시점에 필요한 회의실 수를 따질 수 있다.

 앞에서 등장한 시점들 중 가장 큰 회의실 수를 따로 저장해두고 매 탐색마다 갱신해준 뒤, 탐색 종료 후 그 값을 출력해주면 문제에서 요구하는 답을 출력할 수 있다.

 

 나는 Meeting 클래스를 생성해, 비교 연산자를 종료 시각 기준으로 오버라이딩 해 우선순위 큐에 반영되게 했다. 그리고 시작 시각 순 초기 정렬을 위해 따로 cmp 함수를 생성해 sort()에 comparsion functor로 전달했다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Meeting {
public:
    int start, end;

    Meeting(int start, int end) {
        this->start = start;
        this->end = end;
    }

    bool operator < (const Meeting& other) const{
        return this->end > other.end;
    }
};

bool cmp (Meeting l, Meeting r) {
    return l.start < r.start;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<Meeting> mList;
    priority_queue<Meeting> pq;

    for(int i=0; i<n; i++) {
        int s, e;
        cin >> s >> e;
        mList.push_back(Meeting(s, e));
    }

    sort(mList.begin(), mList.end(), cmp);

    size_t room = 1;
    for(auto m: mList) {
        while(!pq.empty()) {
            if(pq.top().end<=m.start) {
                pq.pop();
            }else {
                break;
            }
        }
        pq.push(m);

        if(room<pq.size()) {
            room = pq.size();
        }
    }

    cout << room;
}