프로그래머스 - Level 2. 피로도 / JavaScript (js)

문제설명

문제분석

모든 던전에는 최소 필요 피로도와 소모 피로도가 존재한다. 최소 필요 피로도보다 현재 남아있는 피로도가 적다면, 해당 던전을 탐색할 수 없다. 당연히 소모 피로도보다 현재 남아있는 피로도가 더 높아야 하며, 가장 효율적으로 많은 던전을 탐색하기 위한 방법을 찾는 문제이다. 말이 조금 어려운 거 같아서 풀어보자면 다음과 같다.

1. 모든 던전에는 [최소 필요 피로도, 소모 피로도]가 존재한다.
2. 모든 던전을 순차적으로 탐색할 때, 가장 많은 던전을 탐색할 수 있어야 한다.
3. 각 던전에 방문하는 모든 경우의 수 중에서, 가장 많은 던전을 탐색하는 경우를 찾는다.
4. 이때 방문할 수 있는 가장 많은 던전의 수가 정답이다.

 

문제를 단순화 했으니 이해하기 쉽게 코드를 짜보자.

반응형

이해하기 쉽게 코드작성하기

function solution(k, dungeons) {
    let answer = -1;
    // 방문했는지 기록
    const isVisited = new Array(dungeons.length).fill(false);
    // 최소 필요 피로도와 소모 피로도를 기록
    const needEnergy = [],
          useEnergy = [];
    dungeons.forEach(([nE, uE]) => {
        needEnergy.push(nE);
        useEnergy.push(uE);
    });
    
    // dfs로 모든 경우의 수 탐색 및 answer 업데이트
    function dfs(count, remain) {
        for(let i = 0; i < dungeons.length; i++) {
            if(isVisited[i] === false
              && needEnergy[i] <= remain) {
                isVisited[i] = true;
                dfs(count + 1, remain - useEnergy[i]);
                isVisited[i] = false;
            }
        }
        answer = Math.max(answer, count);
    }
    
    dfs(0, k);
    
    return answer;
}

코드 설명

가능한 모든 던전을 탐색해야 하기때문에 DFS를 사용했다. 이때 외부 변수 answer를 업데이트 해야해서 solution 함수 내에서 answer를 업데이트 해주었다. 

 

이 코드를 굳이 수정한다면 TypeScript 형태로 가다듬는 일이다. 그러나 js에서는 타입스크립트처럼 interface를 지정할 수 없으니, 아쉬운대로 클래식한 class를 사용해보았다.

// 각 던전에 필요한 데이터
class EnergyData {
    constructor(nE, uE) {
        this.isVisited = false;
        this.needEnergy = nE;
        this.useEnergy = uE;
    }
}

function solution(k, dungeons) {
    let answer = -1;
    const data = [];
    
    // 각 던전 별 데이터 업데이트
    dungeons.forEach(x => data.push(new EnergyData(...x)));
    
    // 함수 내에서 1회 호출하므로 즉시 실행으로 변경
    (function dfs(count, remain) {
        for(let i = 0; i < dungeons.length; i++) {
            if(data[i].isVisited === false
              && data[i].needEnergy <= remain) {
                data[i].isVisited = true;
                dfs(count + 1, remain - data[i].useEnergy);
                data[i].isVisited = false;
            }
        }
        answer = Math.max(answer, count);
    })(0, k);
    
    return answer;
}

dfs 함수를 추상화했다고 가정하고 solution 함수만 놓고보면 훨씬 코드가 깔끔해졌다. 3개의 배열을 하나의 배열로 축소한 게 코드를 깔끔하게 하는 데에 큰 도움이 된 거 같다. 내일부터는 책도 조금씩 읽으면서 자기계발을 시작해보겠다.