(프로그래머스 KAKAO JS)호텔 방 배정

https://programmers.co.kr/learn/courses/30/lessons/64063?language=javascript 

코딩테스트 연습 - 호텔 방 배정

map과 union find를 조합해서 풀이.

 

우선 room number가 배정되었는지 확인하기 위한 map을 선언.

room_number를 for문으로 순회하여 해당 방이 배정되었는지 find 함수를 통해 찾는다.

 

find 함수

전달받은 number를 key로 하여 map을 탐색.

만약 undefined가 나온다면 배정이 안된 상태를 뜻하기 때문에

number를 key, number + 1을 value로 하여 저장한 후, number를 리턴한다.

 

그렇지 않고 이미 방 배정이 되어 있다면 해당 value의 부모 번호를 find 함수를 통해 재귀적으로 찾는다.

끝까지 간 경우 방 배정이 되어있지 않기 때문에 결국 if문으로 빠지게 된다.

끝까지 간 경우의 방 번호를 리턴하게 되면 이를 newNumber라고 저장한다.

이후, number를 key로, newNumber + 1를 value로 하여 map에 저장한 후, newNumber를 리턴하면 된다.

const solution = (k, room_number) => {
    const answer = [];
    const map = new Map();
 
    const find = (number) => {
        if(!map.get(number)){
            map.set(number, number + 1);
            
            return number;
        }
        
        const newNumber = find(map.get(number));
        
        map.set(number, newNumber + 1);
        
        return newNumber;
    }
    
    for(let i = 0; i < room_number.length; i++){
        const number = find(room_number[i]);
        answer.push(number);
    }
    
    return answer;
}