[JS] 호텔 방 배정

 

union-find 알고리즘을 활용해서 해결하였다.

 

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

프로그래머스

 

문제 자체는 이해하기 어렵지 않은 문제다. 일종의 체이닝을 만들어 주면 되는데, 유니온파인드를 통해서 부모를 큰 값으로 넣는다면 숫자를 넣을 다음 번호를 알 수 있을 것 같다.

 

다만 해당 문제는 K의 값이 10의 12승까지로 매우 큰 수가 나오므로 배열이 아닌 map자료형을 활용해서 구현해주었다!

 

 

 

 

 

 

function solution(k, room_number) {
    const map = new Map()
    
    const getParent = (a) => {
        if(!map.has(a)){
            map.set(a,a)
            return a
        }
        if (a === map.get(a)) return a
        const ret = getParent(map.get(a))
        map.set(a,ret)
        return ret
    }
    
    const union = (a,b) => {
        a = getParent(a)
        b = getParent(b)
        
        if(a>b) map.set(b,a)
        else map.set(a,b)
    }
    
   return room_number.map(v => {
       const num = getParent(v)
       union(v,num+1)
       return num
   })
    
    
}