https://school.programmers.co.kr/learn/courses/30/lessons/155651
문제요약
최소한의 객실만을 사용하여 예약손님을 받으려고 한다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다른 손님들이 사용할 수 있다. 예약 시간이 문자열 형태로 담긴 2차원 배열 'booktime'이 매개변수로 주워질 떄, 최소 객실의 수를 return하는 함수를 만들어라.
제한사항
- 1 ≤ book_time의 길이 ≤ 1,000
- book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열
- [대실 시작 시각, 대실 종료 시각] 형태
- 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지.
- 예약 시각이 자정을 넘어가는 경우는 없음
- 시작 시각은 항상 종료 시각보다 빠름
입출력 예
| book_time | result |
|---|---|
| [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]] | 3 |
| [["09:10", "10:10"], ["10:20", "12:20"]] | 1 |
| [["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]] | 3 |
문제풀이
최소한의 방을 사용하면서 손님을 받으려면, 가능한 하나의 방에 많은 손님들을 배치해야한다. 그러기 위해, 다음과 같은 규칙을 짜 볼 수 있다.
- 입실시간을 기준으로 방을 배정한다.
- 만약 입실시간이 같을 경우, 퇴실시간이 빠른 순으로 배정한다.
- 만약 어느 손님의 입실시간이 이미 배정된 방의 퇴실시간 보다 늦을 경우, 방을 추가적으로 사용하지 말고, 기존의 손님의 방을 사용하여 배치한다.
1번의 경우에 주어진 2차원 배열 'book_time'을 입실시간을 기준으로 오름차순으로 정렬하면서 구현할 수 있다.
방 배정의 경우에는 list 혹은 Queue를 사용할 수 있는데, list의 경우 2번 규칙을 위해 매 반복마다 퇴실시간을 기준으로 오름차순 정렬이 필요하고, Queue의 경우 Priority Queue를 이용한다.
퇴실처리의 경우, 앞에서 사용한 데이터 구조에 따라 제거하는 식으로 한다.
시간 비교를 위해 각 시간들은 hour * 60 + minute 으로 변환하고, 퇴실시간의 경우 청소시간을 고려해 10 을 더 더해준다.
코드
Java
import java.util.*;
class Solution {
public int solution(String[][] book_time) {
int answer = 0;
int[][] array = toIntArray(book_time);
Arrays.sort(array, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
Queue<int[]> room = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
for (int[] times : array) {
while (!room.isEmpty() && room.peek()[1] <= times[0]) {
room.poll();
}
room.add(times);
answer = Math.max(answer, room.size());
}
return answer;
}
private int[][] toIntArray(String[][] book_time) {
int[][] array = new int[book_time.length][book_time[0].length];
for (int i = 0; i < book_time.length; i++) {
String[] times = book_time[i];
array[i][0] = timeToInt(times[0]);
array[i][1] = timeToInt(times[1]) + 10;
}
return array;
}
private int timeToInt(String time) {
String[] temp = time.split(":");
return Integer.parseInt(temp[0]) * 60 + Integer.parseInt(temp[1]);
}
}Python
def solution(book_time : list):
answer = 0
book_time.sort(key=lambda x : (x[0], x[1]))
times = []
room = []
for bt in book_time:
times.append(_decode(bt))
for time in times:
while room and room[0][1] <= time[0]:
room.pop(0)
room.append(time)
room.sort(key=lambda x : (x[1]))
answer = max(answer, len(room))
return answer
def _decode(time):
start, end = time
s = int(start.split(":")[0]) * 60 + int(start.split(":")[1])
e = int(end.split(":")[0]) * 60 + int(end.split(":")[1]) + 10
return [s, e]