[프로그래머스] 피로도 (Lv 2) - javascript

문제

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
 
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
 

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
     

나의 풀이

function solution(k, dungeons) {

    // 배열 numbers: [0,1,2... k-1];
    let numbers = []
    for(let i = 0; i < dungeons.length; i++) {
        numbers.push(i);
    }

    //탐험 가능한 던전 개수
    let answer = 0;

    // 탐험하는 순서가 담긴 순열 구하기
    let permutations = permutation(numbers, numbers.length); 

    permutations.forEach(turn => { // ex) [0,2,1]
        let curPower = k;
        let count = 0;
        turn.forEach(idx => { // ex) 0 -> 2 -> 1
            if(curPower >= dungeons[idx][0]) {
                curPower -= dungeons[idx][1];
                count ++;
            }
        })
        answer = Math.max(answer, count);
    })

    return answer;

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

        arr.forEach((v, idx, arr) => {
            let fixer = v;
            let restArr = arr.filter((e, index) => index !== idx);
            let restPermutations = permutation(restArr, selectNum-1);
            let combineFixed = restPermutations.map(v => [fixer, ...v]);
            result.push(...combineFixed);
        })
        return result;
    }
}

 
던전의 숫자를 배열로 만들어 순열을 구하고, 이를 작동시켜 탐험 가능한 던전 개수를 count에 추가했다.
그 중에서 최대값을 반환하니 답이 나왔다.
 

• 정확도 테스트 결과

  

 

다른 풀이

function solution(k, dungeons) {

    let NumOfDun = dungeons.length;
    let visited = new Array(NumOfDun).fill(0);
    let answer = 0;

    function dfs(k, count) {
        for(let i = 0; i < NumOfDun; i++) {
            if(k >= dungeons[i][0] && !visited[i]) {
                visited[i] = 1;
                dfs(k - dungeons[i][1], count+1);
                visited[i] = 0;
            }
        }
        answer = Math.max(answer, count);
    }

    dfs(k,0);
    return answer;
}

 
visited로 던전 방문 여부를 표시하는 배열을 만들고, dfs로 탐색하는 방식이다.
굳이 순열을 구해서 순회하지 않고 재귀를 사용했다.
 

• dfs(k,count)의 작동 방식
   
  k= 3 , dungeons = [[10,10], [10,10], [10,10]] 일 때,
   

  1. 가능한 맨 첫번째 값이 방문됨 visited = [1,0,0]
     1-1. 그 상태에서 순회 -> 가능한 인덱스 방문 [1,1,0]
     1-1-1. 그 상태에서 순회 -> 가능한 인덱스 방문 [1,1,1] -> 순회 완료 -> count가 3인 상태로 answer이 재할당된다.
     1-2. 다음 순회인 세번째 방문 1,0,1
     1-2-1. 가능한 인덱스 방문 1,1,1 -> 순회 완료 -> count가 3인 상태로 answer 재할당
  2. 가능한 두 번째 값이 방문됨 visited = [0,1,0]
     ...

• 정확도 테스트 결과

  

  
   

---

참고

velog.io/@khw970421/