[프로그래머스] 호텔 대실 / priority_queue

 

Level. 2

 

문제

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다.
한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

* 제한사항
- 1 ≤ book_time의 길이 ≤ 1,000
- book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
   [대실 시작 시각, 대실 종료 시각] 형태입니다.
- 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
   예약 시각이 자정을 넘어가는 경우는 없습니다.
   시작 시각은 항상 종료 시각보다 빠릅니다.

 

풀이

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;

int solution(vector<vector<string>> book_time) {
    int answer = 1;
    vector<pair<int, int>> times;
    
    for(int i; i<book_time.size(); i++){
        pair<int, int> p;
        p.first = stoi(book_time[i][0].substr(0, 2)) * 100 + stoi(book_time[i][0].substr(3, 2));
        p.second = stoi(book_time[i][1].substr(0, 2)) * 100 + stoi(book_time[i][1].substr(3, 2)) + 10;
        if(p.second % 100 >= 60){
            p.second = p.second - 60 + 100;
        }
        times.push_back(p);
    }

    sort(times.begin(), times.end());
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(times[0].second);
    
    for(int i=1; i<times.size(); i++){
        if(pq.top() > times[i].first){
            answer += 1;
        }
        else{
            pq.pop();
        }
        pq.push(times[i].second);
    }

    return answer;
}

 

 

사용한 자료구조

priority_queue 

• 우선순위 큐. 원소 중 가장 큰 값이 top을 유지하도록 설계되어 있는 큐 (내림차순)
• priority_queue<int, vector<int>, greater<int>> 해주어 원소중 가장 작은 값이 top을 유지하도록 해주었다. (오름차순)

해결방법

1. 대실시작시간, 대실종료시간의 자료형을 정수형으로 변경하여 vector에 pair로 저장해 주었다.
2. 데이터가 들어있는 vector을 오름차순 정렬해 주어, 대실시작시간 오름차순으로 정렬해 주었다.
3. 큐에는 대실 종료시간만을 저장해 놓는데, 현재 손님의 대실 시작시간이 큐의 top에 있는 대실 종료시간보다 빠르면 answer를 카운트해 주고,
4. 현재 손님의 대실 종료시간이 큐의 top에 있는 대실 종료시간보다 늦으면 큐를 pop 해주어 top의 데이터를 없애준다. 

 

---

다른 풀이

#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;
}

 

 

---

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

프로그래머스