[프로그래머스] 피로도 - 자바스크립트(js)

https://programmers.co.kr/learn/courses/30/lessons/87946?language=javascript 

코딩테스트 연습 - 피로도

 

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

  result.forEach((v) => {
    let fatigue = k;
    let count = 0;
    for (let i = 0; i < v.length; i++) {
      if (fatigue >= v[i][0]) {
        count++;
        fatigue -= v[i][1];
      } else {
        break;
      }
    }
    maxDungeon = Math.max(maxDungeon, count);
  });

  return maxDungeon;
}

const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((el) => [el]);
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const permutations = getPermutations(rest, selectNumber - 1);
    const attached = permutations.map((el) => [fixed, ...el]);
    results.push(...attached);
  });

  return results;
};

DP문제인가 싶었지만 DP로 해결이 안될 것 같았고, DFS로 풀어도 되지만,

최대 던전 수가 8인 걸 보아 완전탐색으로 풀어도 상관없을 것 같아 완전탐색으로 풀었다. 

모든 순서를 구한 후 순차적으로 돌리면 끝!