[프로그래머스] 위클리챌린지 12주차 (js)

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

코딩테스트 연습 - 12주차

 

function solution(k, dungeons) {
    let answer = 0;
    let permutationDungeons = permutation(dungeons, dungeons.length);
    
    permutationDungeons = permutationDungeons.map((v) => v.split(" ").map((vi) => vi.split(",")));
    
    for(let i = 0; i < permutationDungeons.length; i++){
        let fatigue = k;
        let count = 0;
        for(let j = 0; j < permutationDungeons[i].length; j++){
              if(fatigue >= permutationDungeons[i][j][0]){
                  fatigue -= permutationDungeons[i][j][1];
                  count++;
              }
              if(fatigue < 0){
                  break;
              }
        }
        answer = Math.max(count, answer);
    }
    return answer;
}

function permutation(arr, selectNum){
        let result = [];
        if(selectNum === 1) return arr.filter((v)=> [v]);

        arr.forEach((v,idx,arr)=>{
            const fixer = v;
            const restArr = arr.filter((val, index)=> index !== idx);
            const permuArr = permutation(restArr, selectNum-1);
            const combineFixer = permuArr.map((v)=> fixer + " " + v);
            result.push(...combineFixer);
        })
        return result;
}

 

문제에 던전의 최대 길이는 8이라 명시되어 있어 완전탐색을 이용해 쉽게 풀 수 있었다.

 

dfs를 이용한 풀이보다 효율성은 떨어졌다 ㅠㅠㅠ

 

다음에 dfs가 익숙해지면 이용해 풀어봐야겠다.