[Javascript] 프로그래머스 - 피로도

https://namu.wiki/w/JavaScript

 

문제: https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

문제요약

• 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다.
• "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타낸다.
• 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 반환해라.

 

모든 경우의 수를 찾아내는 문제이므로 DFS 알고리즘을 통해 문제를 해결했다. 

 

 

풀이과정

function solution(k, dungeons) {
  let answer = 0;

  const recur = (currK, count, visit) => {
    for (let i = 0; i < dungeons.length; i++) {
      if (!visit[i] && currK >= dungeons[i][0]) {
        visit[i] = true;
        recur(currK - dungeons[i][1], count + 1, visit);
        visit[i] = false;
      }
    }
    answer = Math.max(answer, count);
  };

  recur(k, 0, {});
  return answer;
}

 

 

참고로 아래는 처음에 작성한 오답 코드이다. 디버깅 결과 문제는 8번째 줄의 currK -= dungeons[i][1]; 였다. currK -= dungeons[i][1]을 해버렸기 때문에 9번째 줄에서 재귀 함수에서 탈출한 뒤 10번째 줄을 실행할 때에도 currK는 여전히 currK에서 dungeons[i][1]을 뺀 값이 된다. 재귀 함수에서 빠져나온 뒤에는 재귀 함수에 적용하기 전의 인자 값이 되어야 하는데 이 부분이 틀린 것이다. 

function wrongSolution(k, dungeons) {
  let answer = 0;

  const recur = (currK, count, visit) => {
    for (let i = 0; i < dungeons.length; i++) {
      if (!visit[i] && currK >= dungeons[i][0]) {
        visit[i] = true;
        currK -= dungeons[i][1];
        recur(currK, count + 1, visit);
        visit[i] = false;
      }
    }
    answer = Math.max(answer, count);
  };

  recur(k, 0, {});
  return answer;
}

 

이 두 함수의 차이에 대해 좀 더 자세히 알고 싶다면 crome 개발자 도구창에서 debugger로 디버깅해보는 걸 추천한다.

// 정답: 3, 결과: 3
debugger
solution(80, [
  [80, 20],
  [50, 40],
  [30, 10],
]); 

// 정답: 3, 결과: 2
debugger
wrongSolution(80, [
  [80, 20],
  [50, 40],
  [30, 10],
]);