[JS] 혼자 놀기의 달인

dfs구조를 통해서 방문 배열을 하나 만든 이후에 이를 테스트 하는 방법으로 만드는 방법과 union-find 를 활용해서 구조를 만드는 것 중에서 고민하다가, 결국 루프를 만드는것이 문제의 의도라고 생각해서 union-find 알고리즘을 활용해서 구현해보았다.

 

 

 

개인적으로 해당 문제가 되게 재밌었다. 예전에 아래 유튜브 영상을 보았던 적이 있는데, 이번 문제에서 나온 것과 비슷한 원리가 담겨져 있다. 영상이 재미있으니 한번씩 보아도 좋을 것 같다.

 

https://www.youtube.com/watch?v=PE4vLbyOgw0 

 

 

const find = (arr,a) => {
    if (arr[a] === a) return a
    
    return (arr[a] = find(arr, arr[a]));
}

const union = (arr,a,b) => {
    a = find(arr,a)
    b = find(arr,b)
    
    if (a<b) arr[b] = arr[a]
    else arr[a] = arr[b]
}

function solution(cards) {
    const ary = [ ... new Array(cards.length+1)].map((_,i) => i)
    cards = [0,...cards]
    for (let i = 1 ; i < cards.length ; i++) {
        union(ary,i,cards[i])
    }
    
    const map = new Map()
    
    for (let i = 1 ; i < ary.length ; i++) {
        const el = find(ary,ary[i])
        
        if (map.has(el)) map.set(el,map.get(el)+1)
        else map.set(el,1)
    }
    const ret = [...map].map(el => el[1]).sort((a,b) =>b-a)
    return ret.length>1 ? ret[0] * ret[1] : 0
}