호텔 대실(39분)

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

구현 아이디어 5분 구현 34분

풀이

1. 빈 방을 넣는 큐와 퇴실 시간 기준 최소힙으로 정렬하는 우선순위 큐를 만든다.
2. 예약 정보를 입실 시간 기준으로 오름차순 정렬한다.
3. 벡터를 돌면서 현재 입실하고 싶은 시간보다 우선순위 큐의 퇴실 시간이 더 빠르다면 그 방을 이용하면 되기 때문에 우선순위 큐에서 해당 예약을 pop 하고 빈 방을 넣는 큐에 방을 추가한다.
4. 큐에 원소가 있다면 pop 하고 사용한다.
5. 큐에 원소가 없다면 방을 추가한다.
6. 우선순위 큐의 사이즈와 큐의 사이즈를 더한 값이 answer가 된다.

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

using namespace std;

// 최소힙.
struct Room
{
    int s;
    int e;
    Room(int s, int e)
    {
        this->s = s;
        this->e = e;
    }
    bool operator<(const Room& b) const
    {
        return e > b.e;
    }
};

struct Book
{
    int s, e;
    Book(int s, int e)
    {
        this->s = s;
        this->e = e;
    }
    bool operator<(const Book& b) const
    {
        return s < b.s;
    }
};

int change(string s)
{
    int h = (s[0] - '0') * 10 + (s[1] - '0');
    int m = (s[3] - '0') * 10 + (s[4] - '0');
    
    return h * 60 + m;
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    int N = book_time.size();
    
    vector<Book> vB;
    queue<int> qR;
    priority_queue<Room> pQR;
    
    for(int i = 0; i < N; ++i)
    {
        int s = change(book_time[i][0]);
        int e = change(book_time[i][1]) + 10;
        vB.push_back(Book(s, e));
    }
    
    sort(vB.begin(), vB.end());
    
    for(int i = 0; i < vB.size(); ++i)
    {
        // 예약 하나를 꺼냈다.
        Book b = vB[i];
        
        // 우선순위 큐에 있는 Room들의 퇴실 시간이 b의 시작 시간보다 빠르면
        // 우선순위 큐에서 꺼내고 빈 방을 넣어두는 큐에 방을 추가한다.
        while(!pQR.empty())
        {
            Room r = pQR.top();
            
            if(r.e <= b.s)
            {
                pQR.pop();
                qR.push(0);
            }
            else break;
        }
        
        // 빈 방을 넣어두는 큐에 방이 있다면.
        if(!qR.empty())
        {
            qR.pop();
            pQR.push(Room(b.s, b.e));
        }
        else
        {
            pQR.push(Room(b.s, b.e));
        }
    }
    
    answer = qR.size() + pQR.size();
    
    return answer;
}