[프로그래머스] Level 2. 호텔 대실

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

프로그래머스

 

 

해결 방법

• 각 고객의 입실,퇴실 정보를 pair<int,int> 로 만들어서 리스트에 넣는다. 10:40 이라면 10*60 + 40 으로 변환하여 int표현이 가능하다.
• 입실이 빠른 고객부터 정렬한다.
• vector<int> rooms 를 선언하고, 각 방의 퇴실시간을 적는다. 입실이 빠른 고객부터, 빈방이 있다면 거기에 들어가고 room[i] = 퇴실시간 + 10분(청소시간) 을 추가한다.
• 모든고객을 처리한 후 rooms의 사이즈를 리턴한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
bool compare(const pair<int,int>& a, const pair<int,int>& b){
    return a.first < b.first;
}

int solution(vector<vector<string>> book_time) {
    vector<pair<int,int>> times;
    
    //time정보 저장
    for(int i=0;i<book_time.size();i++){
         int shour = stoi(book_time[i][0].substr(0,2));
        int sminute =stoi(book_time[i][0].substr(3));
        int fhour = stoi(book_time[i][1].substr(0,2));
        int fminute= stoi(book_time[i][1].substr(3));
        
        times.push_back(make_pair(shour*60+sminute,fhour*60+fminute));
    }

	//입실이 빠른 고객부터 정렬
    sort(times.begin(),times.end(),compare);
    vector<int> rooms;
    
    //빈방을 찾아 순서대로 넣어줌
    for(int i =0;  i<times.size(); i++){
        bool flag =false;
        for(int j =0; j<rooms.size(); j++){         
            if(rooms[j] <= times[i].first){
                flag = true;
                rooms[j] = times[i].second +10;
                break;
            }    
        }
        if(!flag){
          rooms.push_back(times[i].second+10);
        } 
        
    }
    
    return rooms.size();
}

 

 

다른 풀이

우선순위 큐 라는것을 알았다. 큐인데, 숫자가 높은 순서대로 자동정렬을 해준다고 한다.

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

using namespace std;

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> q;
    sort(book_time.begin(), book_time.end());
    for (int i = 0; i < book_time.size(); i++) {
        string st = book_time[i][0];
        string ed = book_time[i][1];
        int stT = stoi(st.substr(0, 2)) * 60 + stoi(st.substr(3));
        int edT = stoi(ed.substr(0, 2)) * 60 + stoi(ed.substr(3)) + 10;
        while (!q.empty() && q.top() <= stT) {
            q.pop();
        }
        q.push(edT);
        answer = max(answer, (int)q.size());
    }
    return answer;
}

 

priority_queue<int, vector<int>, greater<int>> q;

우선순위 큐의 기본은 최대 힙 (Max Hip) , 즉 큰 값이 front로 온다. 이 문제의 경우 퇴실시간이 빠른 순서대로 나열해야 하므로 최소 힙(Min Hip) 을 사용해야 한다. greater<int> 옵션은 작은 순서로 정렬하라는  의미이다.

 

새로운 고객이 들어왔을때, 퇴실작업이 종료된 방들을 모두 제거하고, 자신을 큐에 집어넣는다. 집어넣는 작업이 끝난 후 큐의 사이즈가 answer보다 크다면 저장해놓는다. 

 

정렬이 내부적으로 진행되므로 편한 자료구조인것같다.