[프로그래머스] 피로도 (LV.2) by javascript - 완전탐색

▷ 문제 : 완전탐색 - 피로도 LV.2

프로그래머스

▷ 해결 날짜 : 2022.08.02
▷ 소요 시간 : 40분
▷ 풀이 과정 :

완전탐색 카테고리에 있는 문제이다.

"총 피로도(k)", "던전의 정보(dungeons) - 최소 필요 피로도, 소모 피로도"가 입력으로 주어지며, 최대로 돌 수 있는 던전의 개수를 구해주면 되는 문제이다.

 

단순히 이중 포문 같은 완전 탐색으로는 해결이 불가능한 문제이며, 경우의 수가 필요하다 싶어 "순열"을 이용해 문제를 해결하였다.

 

아마 제한사항에서 배열의 길이가 길면 길어질수록 이 해결방법으로는 풀 수 없는 문제일 텐데, 일단 주어지는 배열의 길이가 길지 않으므로 순열로 해결하는 것으로 마무리를 지었다.

 

다른 사람의 풀이를 보면 "재귀 DFS"를 활용한 풀이로 아주 가볍게 풀어놓았다.

 

▷ 구현

function solution(k, dungeons) {
  var answer = -1;

  const permutaions = getPermutations(dungeons, dungeons.length);
  for (let i = 0; i < permutaions.length; i++) {
    const dungeon = permutaions[i];

    let count = 0;
    let fatigue = k; // fatigue : 피로도...?
    for (let j = 0; j < dungeon.length; j++) {
      const [needFatigue, useFatigue] = dungeon[j];
      if (fatigue >= needFatigue) {
        count++;
        fatigue -= useFatigue;
      }
    }
    answer = Math.max(answer, count);
  }

  return answer;
}

const getPermutations = (arr, num) => {
  if (num === 1) return arr.map((v) => [v]);

  const results = [];
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const permutaions = getPermutations(rest, num - 1);
    const attached = permutaions.map((v) => [fixed, ...v]);
    results.push(...attached);
  });

  return results;
};

▷ 복기 :

DFS/BFS에서 내가 할 줄 아는 거라곤 queue에 값을 집어넣고 while반복문을 돌려서 확인해주는 것뿐인데, 다들 재귀로 풀어버리니 재귀 DFS/BFS에 대해 좀 알아두면 좋을 것 같다.