#1. 문제
#2. 풀이
1. sort
sort 알고리즘은 C++의 STL에서 제공하는 정렬 알고리즘으로, 컨테이너의 begin()과 end()를 전달하고, 정렬 기준을 설정하여 컨테이너 내부 항목들을 기준에 맞춰 정렬하는 알고리즘입니다. sort 알고리즘의 default 정렬 기준은 오름차순입니다.
2. 우선순위 큐
우선순위 큐는 각 항목에 우선순위를 부여하고, 우선순위가 가장 높은 항목에 대해서 삽입/접근/삭제 작업을 허용하는 자료구조입니다. 일반적으로, 우선순위 큐는 최소/최대 힙을 통해 구현가능합니다.
3. 현재 예약 건의 대실 시작 시간과 우선순위 큐의 종료 시간 비교!
- 먼저, 입력으로 주어진 시작 시간과 종료 시간을 파싱 하고, 분 단위로 값을 변경해 주어 pair 형식으로 목록을 구성합니다.
- 만들어진 목록을 first(시작 시간)을 기준으로 오름차순 정렬해 줍니다.
- 다음으로, 우선순위 큐(최소 힙)를 활용하여, 우선순위 큐에서 시작 시간이 가장 빠른 항목의 종료 시간 + 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;
}
'문제 풀이 > Programmers 문제 풀이' 카테고리의 다른 글
[Programmers, C++]#Level2_전력 망을 둘로 나누기, DFS, 깊이 우선 탐색, 재귀 DFS, 트리, 트리의 DFS (0) | 2024.10.08 |
---|---|
[Programmers, C++]#Level2_마법의 엘리베이터, 올림, 내림, 반올림, 10진수 자릿수 구분 (0) | 2024.09.24 |
[Programmers, C++]#Level3_스티커 모으기(2), 동적 계획법, DP, Dynamic Programming, 점화식 (0) | 2024.09.20 |
[Programmers, C++]#Level2_최솟값 만들기, 우선순위 큐, 최소 힙, 최대 힙, 완전 이진 트리 (0) | 2024.09.20 |
[Programmers, C++]#Level2_올바른 괄호, 스택, stack (0) | 2024.09.12 |