[코딩] 최소 방 개수 구하기

사실 영어로 글을 며칠전에 먼저 썼는데 한글로 쓰는게 늦어졌습니다 양해 부탁드립니다…

얼마 전에 이 영상을 보았습니다: https://www.youtube.com/watch?v=INauRP_Ovtk .

초반 부분만 봤는데 제대로 이해한 게 맞다면 문제는 다음과 같은 것 같았습니다:

미팅(이나 인터뷰) 스케줄 짜기
각 미팅은 일정한 기간이 있음.
n개의 미팅이 있을때 필요한 방의 개수를 구하라.

그리고 이렇게 요약해서 보여줬습니다:

그런데 잠깐 보다 보니까 저는 트리나 이런 복잡한 방법을 쓰지 않고 더 쉽게 풀 수 있을 것 같아서 해보기로 했습니다.

제 처음 생각은 다음과 같습니다: 24개의 크기를 갖는 int 배열을 만들고, 0으로 초기화한다. 각 index가 하루 24시에 해당한다. 새 meeting이 입력되면, 그 시간에 해당되는 index에 1씩 더한다. 예를 들어, 오후 2시에서 4시까지 미팅이 있으면, 배열의 14번부터 16번까지 인덱스에 1씩 더한다. 반복하고 끝나면 제일 큰 수를 구한다.

cpp로 짠 코드입니다

class Meeting {

    int startTime;
    int endTime;

    public:
        Meeting() {
            startTime = 0;
            endTime = 0;
        }
        Meeting(int startTime, int endTime) {
            this->startTime = startTime;
            this->endTime = endTime;
        }
        // get start time
        int getStartTime() {
            return startTime;
        }
        // get end time
        int getEndTime() {
            return endTime;
        }
};

int main()
{
    int time[24] = {0};

    std::cout << "Enter the number of meetings: ";
    int n;
    std::cin >> n;

    Meeting *meetings = new Meeting[n];

    for (int i = 0; i < n; i++) {
        std::cout << "Enter the start time and end time of meeting " << i + 1 << ": ";
        int startTime, endTime;
        std::cin >> startTime >> endTime;
        meetings[i] = Meeting(startTime, endTime);
    }

    for (int i = 0; i < n; i++) {
        int startTime = meetings[i].getStartTime();
        int endTime = meetings[i].getEndTime();

        for (int j = startTime; j < endTime; j++) {
            time[j]++;
        }
    }

    int max = 0;
    for (int i = 0; i < 24; i++) {
        if (time[i] > max) {
            max = time[i];
        }
    }

    std::cout << "Maximum number of meetings that can be held in a day(Minimum amount of room required): " << max << std::endl;

    return 0;
}

다만 이 방법은 몇가지 문제가 있을 수 있습니다:

첫번째로 한 미팅이 끝나고 바로 다음 것이 시작할 경우입니다. 예를 들어, 하나가 9시부터 11시까지 진행되고 그 다음것이 바로 11시부터 있는 경우 입니다. 그럴 경우 이 알고리즘에서는 정확히 11시에 2개의 방을 요구할 것입니다. 하지만 프로그램을 사용하는 고객은 하나가 끝나고 그 방에서 바로 다음 미팅을 진행하고 싶어할 수도 있습니다. 지금 상태로 이 알고리즘은 그럴 경우를 처리하지 못합니다. 하지만 적어도 제가 겪었던 실제 업무 미팅들은 제시간에 끝난 적이 없기 때문에, 약간의 보정을 가미했다고 생각하고 일단은 스스로 넘어가겠습니다.

두번째 문제는 시간 단위를 바꿀 경우입니다. 나중에 사용자가 한시간 단위가 아니라 30분 단위, 예를 들어 10시 반에서 12시 반까지의 미팅을 원한다고 할 수도 있습니다. 그럴 경우 당장 생각나는 방법은 배열 크기를 늘리고 인덱싱하는 부분을 좀 손봐야 할 것 같은데, 좀 귀찮고 지저분해진다는 단점이 있습니다.

가끔 이런 과제를 풀어보는 것도 재미있네요. 이런건 어차피 네이버 블로그에 올려도 아무도 안 볼테니 풀게 되면 여기 올리도록 하겠습니다.