<프로그래머스> 호텔 대실(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%ED%98%B8%ED%85%94%20%EB%8C%80%EC%8B%A4

[프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/155651

 

뭔가 문제를 볼 때 필요하거나 가질 수 있는 최소, 최대 값 결과를 원하다면 약간 식은땀이 나고 머릿속에서 '어떤 어려운 알고리즘이 필요한 거지?'라는 생각이 가장 먼저 드는 것 같다.

이 문제도 약간 그렇게 시작을 했다.

 

그래도 머릿속에 떠오른 방법이 있어서 그걸 붙잡고 한발자국씩 걸었다.

여기서 시간을 비교해야했기 때문에 LocalTime이 떠올랐다.

내가 생각해도 신기한 부분인데 보통은 시간이 나오면 분이나 초로 바꿀텐데 LocalTime이라니...

어쨌든 그렇게 입력값을 변환하고 내가 생각한 방법을 코드로 적어나갔다.

필요한 방을 위해 객체를 만들고 각 방을 돌면서 겹치는 부분이 있는지 앞뒤로 확인하고 모두 다 겹치는 부분이 있다면 새롭게 방을 주는 식이었다.

예제는 당연히 통과했고 제출했더니 당연히 실패했다.

그것도 대부분 실패...(시간초과도 아닌데 이렇게 빨간 글씨 많이 본건 오랜만이다.)

 

왜 그럴까... 하다가 pass 변수의 역할이 문제가 있었다고 생각이 들었다.

그래서 Int 타입이었던 pass를 Boolean 타입으로 변경하고 false일 때만 방 비교를 하도록 했다.

이전에는 입력값 하나가 이방 저방을 보고 시간만 맞으면 다 들어갔기 때문이다.

그렇게 제출했는데 딱 하나 더 맞았다...ㅎ

 

살살 멘탈이 흔들리기 시작하는데 이때 힌트를 얻었다.

바로 무작위인 대실 시간을 입실 시간 기준으로 정렬하는 것이다.

그러면 앞뒤로 비교하는 것이 아니라 현재 방의 퇴실시간 + 10 과 들어올 사람의 입실 시간만 비교하면 되기 때문이다.

뭔가 될 거 같아서 기쁜 마음으로 예제 통과 확인하고 제출했는데 절반정도 맞았다...

확실히 정렬이 어느정도 영향이 있었다는 것을 알 수 있었지만 완전 해결까지는 아니었다는 거다.

 

이 타이밍에서 무심코 넘겼었던 부분을 체크했다.

바로 23:59에서 10분을 더하면 LocalTime에서 어떻게 처리가 되는가...!

해봤더니 00:09이 되더라

그렇게 되면 거의 모든 입력 정보의 입실 시간보다 작았을거기 때문에 원하지 않는 값이 나오고 있었음을 예상해볼 수 있다.

그래서 10분을 더했을 때 자정이 넘어갈 수 있는 시간대는 예외처리를 해줬다.

다시 예제 확인하고 제출했더니 드디어 맞았다..!!!!

 

아... 그런데 시간이 너무 걸리더라

그래서 LocalTime으로 받았던 대실 시간들을 Int 타입으로 받고 제출했더니 시간이 줄었다.

LocalTime 타입으로 변환하는데 시간이 좀 걸리는 것 같다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.time.LocalTime
import java.time.format.DateTimeFormatter

class Solution {
    fun solution(book_time: Array<Array<String>>): Int {
        var rooms: Array<Array<Int>> = arrayOf()
        var sortBookTime = book_time.sortedBy { it.first() }.map { it.map { time -> time.slice(0..1).toInt() * 60 + time.slice(3..4).toInt() } }

        rooms += sortBookTime[0].toTypedArray()
        for (i in 1 until sortBookTime.size) {
            val cur = sortBookTime[i]
            var pass = false
            for (j in rooms.indices) {
                if (rooms[j][1] + 10 <= cur[0] && !pass) {
                    rooms[j][1] = cur[1]
                    pass = true
                    break
                }
            }
            if (!pass) rooms += cur.toTypedArray()
        }

        return rooms.size
    }
}

 

다 마치고 다른 사람들의 풀이를 보는데 대부분 입실 시간과 퇴실 시간을 세팅할 때 퇴실 시간에 +10을 미리 해놓더라

그리고 방법들에는 우선순위큐를 써서 퇴실시간이 빠른 값이 먼저 나가도록 세팅하는 방법, 하루가 1440분이라는 걸 이용해서 사용되는 시간의 배열값을 증가시키는 방법, 입실 시간과 퇴실시간을 함께 오름차순 정렬하여 stack으로 현재 사용되는 방 개수를 구하는 방법 등 다양한 방법들이 있더라

확실히 내가 문제를 너무 어렵게 생각했던 거 같다...