📌 출처
📝 문제 설명
호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 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" 까지로 주어집니다.
- 예약 시각이 자정을 넘어가는 경우는 없습니다.
시작 시각은 항상 종료 시각보다 빠릅니다.
- book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
⌨ 입출력 예
| targets | 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
첫 번째 손님이 10시 10분에 퇴실 후 10분간 청소한 뒤 두 번째 손님이 10시 20분에 입실하여 사용할 수 있으므로 방은 1개만 필요합니다.
입출력 예 #3
세 손님 모두 동일한 시간대를 예약했기 때문에 3개의 방이 필요합니다.
💻 내 코드
1. 리스트를 사용하여 구현
import java.util.*;
class Solution {
public int solution(String[][] book_time) {
int answer = 0;
int[] rooms = new int[60 * 24 + 10];
for(String[] time : book_time) {
String start = time[0];
String end = time[1];
rooms[calTime(start)] += 1;
rooms[calTime(end) + 10] -= 1;
}
for(int i = 1; i < rooms.length - 1; i++) {
rooms[i] += rooms[i - 1];
answer = Math.max(rooms[i], answer);
}
return answer;
}
public int calTime(String time) {
String[] timeArr = time.split(":");
String hour = timeArr[0];
String minute = timeArr[1];
return Integer.parseInt(hour) * 60 + Integer.parseInt(minute);
}
}✏ 설명
누적합 문제!!
일반적으로 배열에 공간이 비어있는지 확인하기 위해서는 0과 0이 아닌 숫자를 사용한다.
0은 비어있다는 뜻이고, 0이 아니면 공간이 차 있다는 뜻이다.
[3, 7]까지 배열로 공간을 채워보면 다음과 같다.
여기에 추가로 [4, 8]까지의 공간을 채워보면 다음과 같다.
이렇게 연속된 공간을 채우는 방법은 일반적으로 두 번의 반복문을 사용한다.
int[] arr = new int[11];
for(int i=3; i<=7; i++) arr[i] += 1;
for(int i=4; i<=8; i++) arr[i] += 1;이 방법의 경우 배열을 많이 채워야 하면 시간이 오래 걸리게 된다.
이 걸 단 한번의 반복문으로 끝낼 수 있게 하는 방법이 누적합이다.
우선, 시작 위치에 1을 추가하고 (끝 + 1) 위치에 -1을 추가한다.
그 후, 뒤로 진행하면서 이전의 값을 더하면 된다.
[3, 7]과 [4, 8]의 시작 위치는 각각 3과 4이다.
(끝 + 1)은 8과 9이다.
이를 표현하면 다음과 같다.
이제 누적합을 진행한다.
누적합은 현재 위치에 이전 위치의 값을 더하면 된다.
int[] arr = new int[11];
arr[3] = 1;
arr[4] = 1;
arr[8] = -1;
arr[9] = -1;
for(int i=1; i<11; i++) arr[i] += arr[i-1];
이 방법을 이용해서 분 단위로 배열을 생성한 다음 예약들이 언제부터 언제까지 돼있는지 확인 후 누적합을 실시한다.
다만 위의 예에서는 (끝 + 1) 부분에 -1을 해주었지만 해당 문제에서는 끝 부분에 -1을 해주었다.
rooms[calTime(end) + 10] -= 1;이렇게 한 이유는 위의 예에서는 끝남과 동시에 시작을 할 수 없지만 해당 문제에서는 끝남과 동시에 시작을 할 수 있기 때문이다.
또한, 종료 시간에 청소 시간 10분까지 추가해서 종료 시간을 계산하였다.
이 누적합은 아주 유용하게 쓰일 것 같다.
확실하게 기억해두어야겠다.
