꒰ྀི 08. 프로그래머스:: 피로도

문제 설명

 

유저는 여러 던전을 탐험할 수 있음.

탐험을 시작하기 위해 필요한 최소 필요 피로도와

탐험을 마쳤을 때 소모되는 소모 피로도가 존재함.

 

유저는 현재 피로도를 기반으로 최대한 많은 던전을 탐험하고자 함.

이때 유저가 탐험할 수 있는 최대 던전의 수는?

자료구조

 

주어진 던전의 모든 탐험 순서를 시도해 유저가 탐험할 수 있는 최대 던전 수를 구해야함.

던전의 수는 최대 8개이기 때문에, 완전탐색을 활용해 풀이함.

문제 해결

 

1. 모든 던전 순열 생성

2. 각 순열에 대한 던전 탐험

3. 최대 탐험 던전 수 계산

 

function getPermutations(arr, length) {
    if (length === 1) return arr.map(v => [v]);
    const permutations = [];
    arr.forEach((item, index, array) => {
        const rest = array.slice(0, index).concat(array.slice(index + 1));
        const restPermutations = getPermutations(rest, length - 1);
        const attached = restPermutations.map(permutation => [item, ...permutation]);
        permutations.push(...attached);
    });
    return permutations;
}

function solution(k, dungeons) {
    const permutations = getPermutations(dungeons, dungeons.length);
    let maxDungeonCount = 0;

    permutations.forEach(permutation => {
        let currentFatigue = k;
        let dungeonCount = 0;

        for (let [minFatigue, consumeFatigue] of permutation) {
            if (currentFatigue >= minFatigue) {
                currentFatigue -= consumeFatigue;
                dungeonCount++;
            } else {
                break;
            }
        }

        if (dungeonCount > maxDungeonCount) {
            maxDungeonCount = dungeonCount;
        }
    });

    return maxDungeonCount;
}

 

문제를 푸는 것도 문제인데,

이런 유형의 문제는 변수 이름 정하기가 가장 어렵다.

 

더 간결해보이는 다른 사람의 코드가 있다.

이 경우는 깊이 우선 탐색(DFS)를 사용했다.

 

function solution(k, d) {
    const N = d.length
    const visited = new Array(N).fill(0)
    let ans = 0

    function dfs(k, cnt){
        ans = Math.max(cnt, ans)

        for (let j = 0; j < N; j++){
            if (k >= d[j][0] && !visited[j]){
                visited[j] = 1
                dfs(k - d[j][1], cnt + 1)
                visited[j] = 0
            }
        }
    }

    dfs(k, 0)
    return ans;
}

 

DFS는 모든 가능한 탐험 경로를 탐색하면서 중복 계산을 피할 수 있다.

던전의 개수가 적기 때문에 DFS를 활용하는 것이 충분히 효율적이다.

 

완전 탐색	DFS
던전의 개수가 많아지면 비효율적	방문 배열을 사용하기 때문에 중복 계산을 피함