호텔 대실

링크텍스트

문제 설명

1. book_time[입실 시간, 퇴실 시간]이다. 시간이 겹치지 않게 최소한의 방을 할당하여 그 방의 수를 반환한다.

시행착오 및 문제 풀이

정답 풀이

1. 계산의 용이성을 위해 String형의 시간 단위를 int형의 분 단위로 변환한다. 이때, 퇴실 시 청소 시간 10분을 더해준다.

2. 입실 시간순으로 오름차순 정렬해준다.

3. 이중 for문을 돌며 방 추가 여부를 결정한다.
   3-1. list에 넣어 놓은 퇴실 시간이 현재 예약의 입실 시간보다 작거나 같으면 해당 방 대실 가능하다. 그러므로 list의 퇴실 시간을 새로운 예약 퇴실 시간으로 갱신한다.

   list에 있는 방을 돌며 확인해준다. 만약 예약이 가능한(기존의 방) 방이 생긴다면 check = true로 설정해준다. (방 예약에 성공했다는 뜻)

   예약을 하였으므로 break해서 해당 for문을 나와준다.

   3-2. check가 여전히 false라면 모든 list를 돌며 방을 찾았지만 예약에 실패했다는 뜻이다. 그러므로 list에 해당 예약의 퇴실 시간을 추가해준다. (새로운 방 추가)

4. list의 길이는 방의 갯수와 같다. 반환해준다.

정답 코드

import java.util.*;
class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        
        int[][] time = new int[book_time.length][2];
        int idx = 0;
        
        //시간을 분 단위로 변환
        for(String[] t:book_time) {
            String[] temp1 = t[0].split(":");
            String[] temp2 = t[1].split(":");
            
            time[idx][0] = Integer.parseInt(temp1[0])*60 + Integer.parseInt(temp1[1]);
            time[idx][1] = Integer.parseInt(temp2[0])*60 + Integer.parseInt(temp2[1]) + 10;
            
            idx++;
        }
        
        //입실 시간순으로 오름차순 정렬
        Arrays.sort(time, (o1, o2) -> Integer.compare(o1[0],o2[0]));
        
        ArrayList<Integer> room = new ArrayList<>();
        
        for(int[] t:time) {
            //확인
            boolean check = false;
            
            for(int i=0; i<room.size(); i++) {
                //입실시간이 퇴실시간보다 크거나 같은 경우 해당 방 대실 가능
                if(room.get(i) <= t[0]) {
                    //i번 방에 퇴실 시간을 현재 예약의 퇴실 시간으로 수정
                    room.set(i, t[1]);
                    check = true;
                    break;
                }
            }
            
            //새로운 방이 필요한 경우
            if(!check) {
                room.add(t[1]);
            }
        }

        return room.size();
    }
        
      
}

정답~!!

이제 시행착오에 대해 설명하겠다.

틀린 코드

import java.util.*;
class Solution {
    public int solution(String[][] book_time) {
        int answer = 1;
        
        int[][] time = new int[book_time.length][2];
        int idx = 0;
        
        //시간을 분 단위로 변환
        for(String[] t:book_time) {
            String[] temp1 = t[0].split(":");
            String[] temp2 = t[1].split(":");
            
            time[idx][0] = Integer.parseInt(temp1[0])*60 + Integer.parseInt(temp1[1]);
            time[idx][1] = Integer.parseInt(temp2[0])*60 + Integer.parseInt(temp2[1]) + 10;
            
            idx++;
        }
        
        //입실 시간순으로 오름차순 정렬
        Arrays.sort(time, (o1, o2) -> Integer.compare(o1[0],o2[0]));
        
        ArrayList<Integer> room = new ArrayList<>();
        room.add(time[0][1]);
        
        for(int[] t:time) {
            for(int i=0; i<room.size(); i++) {
                //입실시간이 퇴실시간보다 크거나 같은 경우 해당 방 대실 가능
                if(room.get(i) <= t[0]) {
                    //i번 방에 퇴실 시간을 현재 예약의 퇴실 시간으로 수정
                    room.set(i, t[1]);
                }
                //새로운 방 필요
                else {
                    room.add(t[1]);

                }
            }
        }

        return room.size(); // 필요한 최소 방 수
    }
}

결과: 메모리 초과....?!

why...?
아! 안쪽 for문 안에서 새로운 방을 추가하는 부분이 틀렸구나!
예를 들어서, 만약 방이 1,2 총 2개인데 현재 예약이 방1에는 못들어가지만 방2에 들어갈 수 있는 경우가 있다고 생각해보자.
오답코드대로 하면 1번방에서 예약이 안되었으므로 바로 새로운 방을 추가해버린다. 그러면 방의 갯수가 기하급수적으로 늘어난다. 그렇기 때문에 메모리 초과가 발생한듯하다..!!

for문 다 돌리고! 리스트에 있는 방 다 확인해보고! 그럼에도 방이 없으면 추가하는~ 그런 느낌으로~ 오키~

새롭게 알게된 점

//입실 시간순으로 오름차순 정렬
Arrays.sort(time, (o1, o2) -> Integer.compare(o1[0],o2[0]));
        

(o1,o2) -> Integer.compare(o1[0], o2[0])

2개의 배열에서 첫번째 값(입실 시간)을 비교하여 오름차순으로 정렬하였다.
Integer.compare() 처음 봤는데 편하다. 애용하겠소

---

마지막 부분이 좀 헷갈렸던 것 같다 떼잉