오늘은 ⭐호텔 대실 이라는 문제를 풀어보았다.
0. 문제 설명
- 손님들이 호텔 대실을 ["HH:MM", "HH:MM"] 형태로 한다. 시작 시간과 종료 시간이다.
- 호텔 대실 종료 후 청소 시간 10분이 필요하다.
- 손님들의 예약이 겹치치 않도록 최소의 방의 개수를 구해야 한다.
1. 접근법
새로운 방이 필요한지 알기 위한 조건
-> 현재 예약 시간이 겹치는지 알아야 함
-> 어떻게?
1. 현재 예약 시작 시간 < 다른 예약 종료 시간
: 현재 예약 종료 시간 <= 다른 예약 시작 시간 인지 확인. 아니면 새 방 필요
- 현재 예약 시작 시간 >= 다른 예약 종료 시간 (청소 시간 이미 계산 됨을 전제)
: 방 내줄 필요 없음
[접근법]
1. 큐 리스트를 만든다. (1000개). (큐 리스트 인덱스 포인터+1)==필요한 방의 개수
2. 입력을 받을 때마다 0번째 인덱스~현재 큐 리스트 인덱스 포인터까지 모든 방을 위 조건대로 점검한다.
3. 끝까지 돌았을 때 방을 새로 내어줄 필요가 없으면, 넣어줄 수 있는 곳에 넣는다.
4. 끝까지 돌았을 때 방을 새로 내어줘야 한다면, 큐 리스트 인덱스 포인터를 하나 늘리고, 해당 큐에 입력값을 넣어준다.
[입력]
- 모든 큐에는 room 이란 클래스로 들어간다.
- 필드로는 시작시간과 종료시간을 0000의 숫자 형태로 가진다.
- 종료 시간은 청소시간 10분을 사전에 추가한 채로 로직을 진행한다.
2. 문제점
위와 같은 로직으로 코드를 짰는데, 너무 충격적이게도 틀렸다는 판단을 받았다. 이유는 다음과 같다.
다음과 같은 예약이 있다고 가정해보자.
[["11:00", "11:30"], ["10:00", "10:10"], ["10:05", "10:15"]]
내 로직은 입력 순으로 처리한다. 그렇다면 다음과 같이 예약이 될 것이다.
Room 1 : ["11:00", "11:30"], ["10:00", "10:10"]
Room 2 : ["10:05", "10:15"]
그러나 이는 예약을 시간순으로 정렬 후 로직을 진행하면 다음과 같이 들어간다.
Room 1 : ["10:00", "10:10"], ["11:00", "11:30"]
Room 2 : ["10:05", "10:15"]
살짝 방의 구조가 달라지는 것을 알 수 있다. 지피티와 1시간을 붙들고 반례케이스를 찾아보고자 노력했으나,,, 찾지는 못했다.
일단 로직 진행 전, 예약을 정렬해주어야 했고 다음 코드 한 줄을 추가하니 통과했다!
Arrays.sort(book_time, (a, b) -> timeConverter(a[0]) - timeConverter(b[0]));
3. 코드
import java.util.*;
import java.io.*;
class Room {
int start;
int end;
public Room(int s, int e) {
this.start=s;
this.end=e;
}
}
class Solution {
public List<Room>[] roomsInfo = new ArrayList[1000];
public int qIdx=0;
public int solution(String[][] book_time) {
for(int i=0; i<1000; i++) {
roomsInfo[i] = new ArrayList<>();
}
Arrays.sort(book_time, (a, b) -> timeConverter(a[0]) - timeConverter(b[0]));
for(int i=0; i<book_time.length; i++) {
checkRoom(new Room(timeConverter(book_time[i][0]), timeConverter(book_time[i][1])+10));
}
return qIdx+1;
}
public int timeConverter(String s) {
String [] arr = s.split(":");
int start = Integer.parseInt(arr[0]);
int end = Integer.parseInt(arr[1]);
return start*60 + end;
}
public void checkRoom(Room newR) {
boolean isNeedNew=false;
int canPutIdx = -1;
/*
1. 현재 예약 시작 시간 < 다른 예약 종료 시간
: 현재 예약 종료 시간 < 다른 예약 시작 시간 인지 확인. 아니면 ++
2. 현재 예약 시작 시간 >= 다른 예약 종료 시간 (청소 시간 이미 계산 됨을 전제)
: 방 내줄 필요 없음
*/
for(int i=0; i<=qIdx; i++) {
isNeedNew = false;
for(int j=0; j<roomsInfo[i].size(); j++) {
Room usedR = roomsInfo[i].get(j);
if(newR.start < usedR.end && newR.end > usedR.start) {
isNeedNew = true;
break;
}
}
if(!isNeedNew) {
canPutIdx = i;
break;
}
}
if(!isNeedNew) {
roomsInfo[canPutIdx].add(newR);
//System.out.printf("기존 방 %d에 추가. 시작 시간 : %d, 종료 시간 : %d \n", canPutIdx, newR.start, newR.end);
}
else {
roomsInfo[++qIdx].add(newR);
//System.out.printf("새로운 방 %d에 추가. 시작 시간 : %d, 종료 시간 : %d \n", qIdx, newR.start, newR.end);
}
}
}