호텔 대실 | 프로그래머스

📍 호텔 대실

💡 문제

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 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" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

✅ 풀이

👆 첫 번째 풀이 (성공)

주석으로 작성해보았다... 거지깽깽이 같던 알고리즘 문제만 보다(내가 그냥 멍청한 것임) 이렇게 재밌는 문제를 풀게 되다니 눈물이 날 뻔 했다. 최고 짱짱 나이스나이스.

class Solution {
    fun solution(book_time: Array<Array<String>>): Int {
        //  체크인 시간과 체크아웃 시간은 최소 10분 차이
        //  첫번째 손님의 체크아웃 시간과 두번째 손님의 체크인 시간 차이가 최소일 때, 최소 방 개수를 구할 수 있다.
        
        // 체크인 시간 기준 오름 차순 정렬 후 숫자 형식으로 변환
        val times = book_time.sortedBy { it[0] }.map { it.map { time -> time.split(":").map(String::toInt) } }
        val booked = BooleanArray(book_time.size) { false }
        var answer: Int = 0
        
        repeat(book_time.size) {
            if (!booked[it]) {
                // 예약을 하지 않았다면,
                // 이전에 할 수 있던 예약이 없던 것.
                // + 이후에 할 수 있는 예약 카운트 
                // (체크인 시간이 현재 손님의 체크아웃 시간보다 10분 뒤에 있어야 함)
                
                // hour * 60 + minute
                var checkout = times[it][1][0]*60 + times[it][1][1] + 10
                booked[it] = true
                answer++
                (it until book_time.size).forEach { index -> 
                    val checkin = times[index][0][0]*60 + times[index][0][1]
                    if (!booked[index] && checkout <= checkin) {
                        checkout = times[index][1][0]*60 + times[index][1][1] + 10
                        booked[index] = true
                    }
                }
            }
        }
        
        return answer
    }
}

🔥 다른 사람의 풀이

나는 정렬을 해서 0번째 사람일 땐 1~마지막 사람, 1번째 사람일 땐 2~마지막 사람 이런식으로 탐색을 했었다. 가져온 풀이는 아예 24시간 + 청소시간 10분까지의 배열을 만들고 각 방이 차지하는 시간을 나타내는 인덱스의 값을 1씩 추가해 가장 많이 겹치는 시간대의 값(배열의 최대값)을 답으로 구했다.

문제에서 주어진 예시 설명에 나온 사진을 보면 가장 많이 겹친 시간대에, 겹쳐진 수가 곧 방의 수라는 걸 알 수 있다.

굳이 정렬할 필요가 없는 풀이라서 좋아보여 가져와보았다.

class Solution {
    fun solution(book_time: Array<Array<String>>): Int {
        var arr = IntArray(1 + 24 * 60 + 10)

        for(times in book_time){
            var startH = times[0].split(":")[0].toInt()
            var startM = times[0].split(":")[1].toInt()
            var EndH = times[1].split(":")[0].toInt()
            var EndM = times[1].split(":")[1].toInt()

            for(i in startH*60 + startM..EndH*60 + EndM + 9){
                arr[i] = arr[i]+1
            }
        }
        return arr.maxOf{it}
    }
}

💭 후기

오랜만에 알고리즘을 몰라도 풀 수 있는 문제라서 너무너무너무너무너무 좋았다. 알고리즘을 공부하면 알고리즘 문제를 풀 때 재미있어질까? 공부할 게 너무 많다.