[Programmers, C++]#Level2_ 호텔 대실, substr, sort 알고리즘, 우선순위 큐, 최소 힙 우선순위 큐

#1. 문제

프로그래머스

 

 

---

 

#2. 풀이

 

1. sort

[Basic C++] #32-3_STL 정렬 알고리즘

sort 알고리즘은 C++의 STL에서 제공하는 정렬 알고리즘으로, 컨테이너의 begin()과 end()를 전달하고, 정렬 기준을 설정하여 컨테이너 내부 항목들을 기준에 맞춰 정렬하는 알고리즘입니다. sort 알고리즘의 default 정렬 기준은 오름차순입니다.

 

2. 우선순위 큐

[Basic C++] #69_priority_queue

우선순위 큐는 각 항목에 우선순위를 부여하고, 우선순위가 가장 높은 항목에 대해서 삽입/접근/삭제 작업을 허용하는 자료구조입니다. 일반적으로, 우선순위 큐는 최소/최대 힙을 통해 구현가능합니다. 

 

3. 현재 예약 건의 대실 시작 시간과 우선순위 큐의 종료 시간 비교!

1. 먼저, 입력으로 주어진 시작 시간과 종료 시간을 파싱 하고, 분 단위로 값을 변경해 주어 pair 형식으로 목록을 구성합니다.
2. 만들어진 목록을 first(시작 시간)을 기준으로 오름차순 정렬해 줍니다.
3. 다음으로, 우선순위 큐(최소 힙)를 활용하여, 우선순위 큐에서 시작 시간이 가장 빠른 항목의 종료 시간 + 10과 현재 순회 중인 항목의 시작 시간을 비교하고, 새로운 방이 필요 없는지 확인해 줍니다.

 

---

 

#3. 코드

@@ -0,0 +1,61 @@
/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/155651
    @문제: 호텔 대실
    @설명
        1. 정렬: 예악 시작 시간 기준 오름차순 정렬
        2. 우선순위 큐(최소 힙): 호텔 각 방의 예약 종료 시간을 기준으로 최소 힙 구성
*/

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

typedef pair<int,int> p;

int solution(vector<vector<string>> book_time) {
    int answer = 0;

    //@ {시작 시간, 종료 시간}
    vector<p> books;

    //@':' 기준 왼쪽을 first, 오른쪽을 second로 파싱
    for(int i=0; i<book_time.size(); ++i)
    {
        int startHour = stoi(book_time[i][0].substr(0, 2));
        int startTimeInMin = startHour * 60 + stoi(book_time[i][0].substr(3,2));

        int endHour = stoi(book_time[i][1].substr(0, 2));
        int endTimeInMin = endHour * 60 + stoi(book_time[i][1].substr(3,2));

        books.push_back({startTimeInMin, endTimeInMin});
    }

    //@시작 시간 기준 오름차순 정렬
    sort(begin(books), end(books), [](const p& a, const p& b)
    {
        return a.first < b.first;
    });

    //@종료 시간 기준 '최소 힙' 구성
    priority_queue<int, vector<int>, greater<int>> pq;
 
    //@우선순위 큐 활용
    for(int i=0; i<(int)books.size(); ++i)
    {
        //@최소 종료 시간 + 10 과 현재 예약 시작 시간 비교
        if(!pq.empty() && pq.top()+10 <= books[i].first)
        {
            pq.pop();
        }
        else
        {
            answer++;
        }
        
        pq.push(books[i].second);
    }

    return answer;
}

 

---