프로그래머스) 호텔 대실
사용 언어: java11
문제를 풀고 나서 다른 분들의 풀이를 살펴보니 조금 더 간결한 코드로 정답을 맞추게 되어 공유하게 됐습니다.
테스트 통과 시간을 비교했을 때 1-2 밀리초 더 빠른 시간을 보였습니다.
그럼 거두절미하고 바로 문제 풀이 방법에 대해 설명드리도록 하겠습니다.
접근 방법
위의 예제를 참고하니 시간이 겹치는 부분마다 무조건 방을 늘릴 수 밖에 없었습니다.
그래서 시간테이블 배열(timeTable)을 하나 만들어 예약 시간부터 청소 시간을 포함한 퇴실 시간까지 1씩 더하는 방법을 떠올렸습니다.
먼저 book_time의 길이만큼 timeTable에서 예약 시간과 청소를 포함한 퇴실 시간까지의 범위를 고려해야 합니다.
- 시각의 범위는 00:00 ~ 23:59인데 시 + 분으로 배열의 크기를 정한다면 23 * 60 + 60 + 10 (10은 청소 시간) 이고 계산하면 총 크기는 1450입니다.
- book_time의 길이는 최대 1000입니다.
- 결국 1000 * 1450 = 1450000 으로 충분히 1초 내에 풀 수 있음을 알 수 있습니다.
이제 배열의 크기까지 알았으니 배열을 초기화하고 시각 범위 내의 index 위치에 1씩 추가합니다.
private static final short MAX = 23 * 60 + 60 + 10;
public int solution(String[][] book_time) {
int[] timeTable = new int[MAX];
for (String[] strings : book_time) {
int start = getMinutes(strings[0]);
int end = getMinutes(strings[1]) + 10;
for (int i = start; i < end; i++) {
timeTable[i]++;
}
}
...주의할 점은 청소가 끝난 시점에 다음 손님을 받을 수 있기 때문에 i의 범위를 end 미만까지 반복문을 돌렸습니다.
이후에 가장 시간이 겹치는 구간(최댓값)을 찾아 정답을 반환합니다.
int answer = 0;
for (int i = 0; i < MAX; i++) {
answer = Math.max(answer, timeTable[i]);
}
return answer;
시간 복잡도
N = book_time의 길이이고, M = 시각의 범위라고 한다면 O(N * M) + O(M) 이고
총 O(N * M)의 시간복잡도를 가집니다.
코드
class Solution {
private static final short MAX = 23 * 60 + 60 + 10;
public int solution(String[][] book_time) {
int[] timeTable = new int[MAX];
for (String[] strings : book_time) {
int start = getMinutes(strings[0]);
int end = getMinutes(strings[1]) + 10;
for (int i = start; i < end; i++) {
timeTable[i]++;
}
}
int answer = 0;
for (int i = 0; i < MAX; i++) {
answer = Math.max(answer, timeTable[i]);
}
return answer;
}
private int getMinutes(String s) {
String[] time = s.split(":");
int hour = Integer.parseInt(time[0]);
int minute = Integer.parseInt(time[1]);
return hour * 60 + minute;
}
}
