[프로그래머스][Kotlin] 2019 카카오 개발자 겨울 인턴십 호텔 방 배정

해당 문제는 유니온파인드 알고리즘 중 파인드의 개념과 map의 개념을 응용하여 작성 할 수 있습니다.

문제를 간단히 설명하자면

 

1.한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2.고객은 투숙하기 원하는 방 번호를 제출합니다.
3.고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4.고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

이때 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

배정 받은 방 번호는 [1,3,4,2,5,6] 입니다.

 

예를 들어 1번 고객이 1번방을 원할 경우 1번방이 map 내 키값이 없다면 1번방을 배정 후 1번방이 다시 호출 될 경우 2번방으로 갈 수 있도록 값을 +1하여 저장 합니다. 그리고 또 다시 다른 고객이 1번방을 원할 경우 현재 원하는 방의 값이 배정이 되어 있는지 확인 후 배정이 안되어 있다면 키값이 1번인 값을 반환합니다. 이때 다른 사람이 2번방을 가지고 있을 경우도 있으니 이때는 2번방을 키로 가지고 있는 값을 반환합니다. 글로는 해당 내용을 어떻게 구현하는지에 대하여 이해가 어려울 것 같아 바로 작성한 코드와 실행결과를 보여드리겠습니다.

 

class Solution {

    var result = HashMap<Long,Long>()

    fun solution(k: Long, room_number: LongArray): LongArray {
        var answer = LongArray(room_number.size)

        for(i in 0 .. room_number.size-1){
            answer[i] = find(room_number[i])
        }
        return answer
    }

    fun find(want:Long):Long{
        if(result[want] == null){ // 원하는 방이 비어 있을 경우
            result[want] = want+1L
            return want
        }
        result[want] = find(result[want]!!) // 원하는 방이 비어 있지 않을 경우
        //ex) 1번방을 원하였으나 배정이 되어 있어 2번방을 배정 하려는데 2번방도 배정이 되어있는 경우
        //    2번방을 키로 가지고 있는 값을 확인하여 재귀 호출
        
        return result[want]!!
    }

}

정확성 테스트

테스트 1 〉	통과 (0.03ms, 60.4MB)
테스트 2 〉	통과 (0.07ms, 62.8MB)
테스트 3 〉	통과 (0.06ms, 60.6MB)
테스트 4 〉	통과 (0.51ms, 60.2MB)
테스트 5 〉	통과 (0.11ms, 62.1MB)
테스트 6 〉	통과 (0.13ms, 62MB)
테스트 7 〉	통과 (0.14ms, 62.1MB)
테스트 8 〉	통과 (0.03ms, 60.8MB)
테스트 9 〉	통과 (0.08ms, 62MB)
테스트 10 〉	통과 (0.11ms, 59.9MB)
테스트 11 〉	통과 (0.08ms, 61MB)
테스트 12 〉	통과 (0.19ms, 62.7MB)
테스트 13 〉	통과 (0.11ms, 61.3MB)
테스트 14 〉	통과 (0.08ms, 62.6MB)
테스트 15 〉	통과 (0.47ms, 62.2MB)
테스트 16 〉	통과 (0.52ms, 62.1MB)
테스트 17 〉	통과 (0.65ms, 60.5MB)
테스트 18 〉	통과 (0.99ms, 60.7MB)
테스트 19 〉	통과 (1.02ms, 61.9MB)
테스트 20 〉	통과 (1.43ms, 63MB)
테스트 21 〉	통과 (2.40ms, 61.6MB)
테스트 22 〉	통과 (1.79ms, 62.2MB)
테스트 23 〉	통과 (1.24ms, 63.6MB)
테스트 24 〉	통과 (3.13ms, 62MB)
테스트 25 〉	통과 (0.16ms, 61.8MB)
테스트 26 〉	통과 (0.41ms, 62.7MB)

효율성 테스트

테스트 1 〉	통과 (345.17ms, 142MB)
테스트 2 〉	통과 (442.29ms, 154MB)
테스트 3 〉	통과 (263.86ms, 127MB)
테스트 4 〉	통과 (314.22ms, 167MB)
테스트 5 〉	통과 (317.48ms, 127MB)
테스트 6 〉	통과 (398.11ms, 179MB)
테스트 7 〉	통과 (334.22ms, 160MB)