[프로그래머스] 호텔 대실(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "호텔 대실" 문제를 해결하는 방법에 대해 설명하려고 합니다. 호텔 운영자가 최소한의 객실을 사용하여 예약된 손님들을 수용하는 방법을 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

문제 개요

"호텔 대실" 문제는 호텔 운영자가 최소한의 객실을 사용하여 예약된 손님들을 수용하는 방법을 찾는 문제입니다. 각 예약은 시작 시간과 종료 시간으로 구성되며, 객실은 퇴실 후 10분간 청소가 필요합니다. 목표는 필요한 최소 객실 수를 찾는 것입니다.

해결 방법

이 문제는 예약 시간을 관리하고, 각 예약에 대해 적절한 객실을 할당하는 알고리즘을 구현하는 데 초점을 맞춥니다. 예약 시간을 분 단위로 변환하고, 현재 사용 가능한 객실을 찾거나 새 객실을 할당하는 방식으로 접근합니다.

코드 구현

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>> table; // 각 객실의 사용 시간을 저장하는 테이블

// 문자열을 구분자에 따라 분할하는 함수
vector<string> Split(string input, string del){
    vector<string> ret;
    string token = "";
    int pos = 0;
    while((pos = input.find(del)) != string::npos){
        token = input.substr(0,pos);
        ret.push_back(token);
        input.erase(0,pos + del.size());
    }
    ret.push_back(input);
    return ret;
}

// 적절한 객실을 찾거나 새 객실을 할당하는 함수
void FindRoom(vector<string> &input){
    vector<string> entry = Split(input[0],":");
    vector<string> exit = Split(input[1],":");
    
    // 입장 시간과 퇴장 시간을 분 단위로 변환
    int entryTime = (atoi(entry[0].c_str()) * 60) + atoi(entry[1].c_str());
    int exitTime = (atoi(exit[0].c_str()) * 60) + atoi(exit[1].c_str());
    
    // 사용 가능한 객실 탐색
    for(int i = 0; i < table.size(); i++){
        pair<int,int> lastTime = table[i].back();
        // 현재 객실 사용이 가능한 경우
        if(lastTime.second + 10 <= entryTime || lastTime.first >= exitTime + 10){
            table[i].push_back({entryTime,exitTime});
            return;
        }
    }
    // 새 객실 할당
    vector<pair<int,int>> temp;
    temp.push_back({entryTime,exitTime});
    table.push_back(temp);
}

// 최소 객실 수를 계산하는 함수
int solution(vector<vector<string>> book_time) {
    int answer = 0;
    sort(book_time.begin(),book_time.end());
    for(int i = 0; i < book_time.size(); i++){
        FindRoom(book_time[i]);
    }
    answer = table.size();
    return answer;
}

코드 설명

이 코드는 예약 시간을 분 단위로 변환하고, 각 예약에 대해 사용 가능한 객실을 찾거나 새 객실을 할당합니다. 예약은 시작 시간 기준으로 정렬되며, 각 예약은 가능한 가장 먼저 사용할 수 있는 객실에 할당됩니다. 최종적으로 객실의 총 수가 필요한 최소 객실 수가 됩니다.

결론

"호텔 대실" 문제는 예약 시간 관리와 효율적인 자원 할당 알고리즘을 통해 해결할 수 있습니다. 이 문제는 시간 관리와 자원 최적화에 대한 이해를 요구하며, 유사한 문제에도 적용될 수 있는 접근 방식입니다.