호텔 방 배정

문제

풀이

효율성에서 상당히 오래 막혀 힘들었는데 한가지 방법을 떠올려 간신히 푸는데 성공했다.

먼저 처음에 실패했던 코드다.

function solution(k, room_number) {
    var answer = [];
    var room = new Map();
    
    for(var n in room_number){
        answer.push(assign(room,room_number[n]))
    }
    
    return answer;
}

const assign = (room,room_number) => room[room_number-1] == null ? room[room_number-1] = room_number: assign(room,room_number+1) 

재귀 함수를 이용해 방이 비어있으면 배정해주고 비어있지 않으면 다음 방을 체크하는 방식을 사용했는데 효율성 검사에서 런타임 에러가 나왔다.

자바스크립트에는 최대 재귀 깊이가 제한되어있어 런타임 에러가 난것으로 생각되어 재귀함수를 빼고 while문을 통해 구현해 보았다.(참고 : https://ko.javascript.info/recursion)

function solution(k, room_number) {
    var answer = [];
    var room = new Map();
    
    for(var n in room_number){
        var tmpList = [];
        while(1){
            if(!room.has(room_number[n])){//방이 비어있을때
                room.set(room_number[n], room_number[n])
                break
            }else{//방에 배정된 사람이 있을때
                room_number[n]++
            }
        }
    }
    return room_number;
}

그런데 이 경우에도 효율성 검사를 통과하지 못했다.

이번에는 런타임 에러는 아니고 단순히 시간 초과였다.

어느 부분에서 시간이 낭비 됐을까 곰곰히 생각해보니 방에 배정된 사람이 있을 때, 다음 방으로 가는 과정이 좀 비효율적이라는 생각이 들었다.

지금까지는 room의 value값은 크게 의미를 두지 않고 있었는데 value값에 다음 찾아가야 할 방이 어디인지를 매번 기록해두고 찾아간다면 방을 찾는 과정을 크게 단축할 수 있지 않을까하는 생각이 들어 다시 고쳐보았다.

function solution(k, room_number) {
    var answer = [];
    var room = new Map();
    
    for(var n in room_number){
        var tmpList = [];
        while(1){
            if(!room.has(room_number[n])){//방이 비어있을때
                room.set(room_number[n], room_number[n]+1)
                for(var tmp in tmpList){
                    room.set(tmpList[tmp], room_number[n]+1)
                }
                break
            }else{//방에 배정된 사람이 있을때
                tmpList.push(room_number[n])
                room_number[n] = room.get(room_number[n])
            }
        }
    }
    return room_number;
}

지금까지 지나온 방들을 기록하는 tmpList를 만들어 지나온 방을 기록하고 비어있는 방을 찾았을 때 지금까지 지나온 방들의 value값에 현재 방의 바로 다음방을 기록해 주었다. 이렇게 하면 다음에 다시 같은 방을 찾게 되면 바로 현재의 다음 방으로 이동하여 시간을 대폭 아낄 수 있을거라 생각했다.

결과는 성공적이었다. 효율성 테스트 7개를 전부 통과하며 문제가 해결됐다.