소요시간 : 약 3시간
오늘의 교훈 : 문제를 꼼꼼히 잘 읽어보자.
문제 접근 방식은 맞았습니다. 시작하는 시간이 가장 중요한 정렬후 그리디 알고리즘을 통해 푸는 문제로
가장 빨리 잡혀있는 예약시간대로 정렬 후에 배열을 돌려 들어갈수 있으면 넘어가지만
들어갈 방이 없다면 방을 하나 추가하는 구조입니다.
정렬은 퀵정렬을 사용하였고 흐름은 아래와 같습니다.
1. 문자열인 시간을 먼저 시간 타입으로 파싱하여 10분을 더해준다.(이부분에 1시간을 잡아먹었다.)
2. 또다른 부분때문에 적어도 2시간 3시간은 잡아먹었던 것 같은데 바로 정각을 넘기지 않는다는 조건이다 그래서 나는 10분을 더했을때 정각이 넘어가면 23시 59분으로 수정했다.
3. 첫번째 순서는 방이 없으니 방을 만들어 첫번째 예약 값을 넣어준다.
4. 예약값의 끝나는 시간만 넣어주고 반복하면 방의 개수를 알수있다.
다른 분들의 풀이를 봤을때 자료구조도 적절이 잘 사용했던것 같은데 (큐 라던가) 나도
잘 사용해봐야 실력이 늘 것같다.
아래 코드 올리며 글 마치겠습니다.
package Question;
import java.time.LocalTime;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.Arrays;
// 프로그래머스 호텔대실
public class HotelRoom {
public static void main(String[] args) {
String[][] time = {{"15:00", "17:00"}, {"16:40", "18:20"}, {"14:20", "15:20"}, {"14:10", "19:20"}, {"18:20", "21:20"}};
System.out.println(solution(time));
String[][] time2 = {{"03:00", "12:50"}, {"01:40", "13:20"},{"00:50", "09:00"}, {"01:20", "23:55"}, {"04:10", "05:20"}, {"00:20", "01:20"}};
System.out.println(solution(time2));
}
// 동일한 시간대면 무조건 방이 그만큼 있어야함
// 각방에는 start 와 end 그리고 end와 새로운 start시간과 비교해야함
// 각 방은 스택으로 쌓임
public static int solution(String[][] book_time) {
int answer = 0;
int[][] dataList = new int[book_time.length][2];
// 정렬 순서
// 가장 빨리 시작하는 시간대
// 스플릿을 통해 앞자리 수치화
for (int i = 0; i < book_time.length; i++) {
int startTime = 0;
int endTime = 0;
// DateTimeFormatter를 사용해 문자열을 LocalTime으로 파싱
DateTimeFormatter formatter = DateTimeFormatter.ofPattern("HH:mm");
LocalTime time = LocalTime.parse(book_time[i][1], formatter);
LocalTime addTime;
addTime = time.plusMinutes(10);
// 원래 자정이 아닌데 10분을 더하니깐 자정이 되었으면 초기화
if (addTime.getHour() == 0 && time.getHour() != 0) {
time = LocalTime.of(23, 59);
}else{
time = time.plusMinutes(10);
}
// 다시 문자열로 변환
String newTimeString = time.format(formatter);
String[] newStartTime = book_time[i][0].split(":");
String[] newTime = newTimeString.split(":");
startTime = Integer.parseInt((newStartTime[0] + newStartTime[1]));
endTime = Integer.parseInt((newTime[0] + newTime[1]));
dataList[i][0] = startTime;
dataList[i][1] = endTime;
}
quickSort(dataList, 0 , dataList.length-1);
System.out.println(Arrays.deepToString(dataList));
ArrayList<Integer> timeList = new ArrayList<>();
for (int[] data : dataList){
if(timeList.isEmpty()){
timeList.add(data[1]);
}else{
boolean find = false;
for (int i = 0; i < timeList.size(); i++) {
if(timeList.get(i) <= data[0]){
timeList.set(i , data[1]);
find = true;
break;
}
}
if(!find){
timeList.add(data[1]);
}
}
}
System.out.println(timeList);
answer = timeList.size();
return answer;
}
static void swap(int[][]a, int idx1, int idx2){
int[] i = a[idx1];
a[idx1] = a[idx2];
a[idx2] = i;
}
static void quickSort(int[][] a, int left, int right){
int pl = left; // 왼쪽 커서
int pr = right; // 오른쪽 커서
int[] x = a[(pl + pr) /2]; // 피벗
do {
while(a[pl][0] < x[0]) pl++;
while(a[pr][0] > x[0]) pr--;
if(pl <= pr){
swap(a,pl++,pr--);
}
}while (pl <= pr);
if(left < pr) quickSort(a, left, pr);
if(pl < right) quickSort(a, pl, right);
}
}
