[JS] 피로도

요즘 완전탐색으로 풀만한 문제들을 해결할때 순열,조합을 연습할 겸 써보고 있다.

 

근데 사실 해당 문제는 순열,조합보다는 그냥 dfs와 visted 배열을 사용했으면 훨씬 빠르게 풀 수 있을거 같긴 하다.

 

 

문제풀이 자체는 조합으로 갈수 있는 던전의 모든 경우의 수를 구한 이후, 각 경우의 수마다 통과할 수 있는 라운드 수를 구해서 더해주었다.

 

 

 

메인 함수 자체의 로직은 되게 간결해졌지만.. dfs로 처리한다면 갈 수 없는 던전의 경우의 수를 상당히 걸러낼 수 있는데 조합으로는 모든 경우의 수를 탐색해보기 때문에 좋은 방식은 아닌 것 같다.

 

문제마다 필요한 방법을 적절히 고려해보는 습관을 들일 필요가 있을 것 같다.

 

 

const getPermutation = (arr,n) => {
    const ret = []
    if (n===1) return arr.map(el => [el])
    
    arr.forEach((fixed,idx,origin) => {
        const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)];
        const permutations = getPermutation(rest,n-1)
        const attached = permutations.map((permutation) => [fixed, ...permutation]);

        ret.push(...attached);
    })
    return ret
}

const getPassRound = (k, dungeons) => {
    let ret = 0
    for (const dungeon of dungeons){
        if (k < dungeon[0]) return ret
        ret++
        k -= dungeon[1]
    }
    return ret
}


function solution(k, dungeons) {    
    return getPermutation(dungeons,dungeons.length).reduce((a,c) => Math.max(getPassRound(k,c),a) , 0)
}