[프로그래머스] Lv2. 피로도 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 피로도

문제

제한사항

📌 내가 생각한 풀이

주어진 제한조건을 보자. 던전의 최대길이 = 8! = 40320 이므로 1억이 넘지 않는다. 즉 모든 경우의 수를 찾은다음, depthResult배열에 넣어 최대값을 찾아주자!

//모든 경우의 수를 찾는 순열 알고리즘.
const permutation = (arr, selectNum) =>{
    let result = [];
    if(selectNum === 1) return arr.map((d)=>[d]);
    arr.forEach((data,idx,origin)=>{
        let rest = [...origin.slice(0,idx), ...origin.slice(idx+1)];
        let permu = permutation(rest,selectNum-1);
        let attached = permu.map((d)=>[data,...d]);
        result.push(...attached);
    })
    return result;
    
}

function solution(k, dungeons) {
    var answer = -1;
    let depthResult = []
    let totalCase = permutation(dungeons, dungeons.length);
    totalCase.map((d)=>{
        let num = k;
        let count = 0;
        for(var i =0; i<d.length; i++){
            if(d[i][0] <= num){
                num-=d[i][1];
                count++;
                
            }
        }
        depthResult.push(count)
    })
    return Math.max(...depthResult)
}

📌 느낀점

제한사항을 보고, 시간복잡도 면에서 초과가 나지 않을 것 같으면, 완전탐색으로 풀리는 문제들이 많다. 제한조건을 꼭 확인하여 문제를 풀어보자!