호텔 방 배정

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

프로그래머스

room 안에 배정된 인원 수가 1 명이므로, has 검사만으로도 충분하다.

요청받은 방 번호가 invalid 하다면, 그 다음으로 큰 번호의 방이 할당되어야 하는데,

iter 를 돌리다보면 O(n) 이 발생하고, 결국 O(n*2) 이 되므로 indexing map 을 두어 접근했다.

 

방을 찾고, 다음에 요청되는 경우 할당 가능한 방을 찾아 이전까지 순회했던 방들의 indxing 도 같이 update 했다.

 

마지막 테스트가 시간초과로 실패했는데, 다른 자료를 찾아보니 js 에서 Object 와 Map 의 퍼포먼스가 크다고 들어

Map 으로 변경하니 해결됐다. 퍼포먼스가 중요한 문제에서는 Map 을 적극 사용하도록 하자.

function solution(k, room_number) {

    var idx_room = new Map();

    function visit(i) {
        var update_list = [i];

        var j = i;
        while (idx_room.has(j)) {
            j = idx_room.get(j);
            update_list.push(j);
        } 
        // find next
        var k = j+1;
        while (idx_room.has(k)) {
            k = idx_room.get(k);
        }
        // update idx
        update_list.forEach(l => {
            idx_room.set(l, k);
        });

        return j;
    }

    return room_number.map(i => visit(i));
}