[Javascript] 피로도 (87946)

문제링크

코딩테스트 연습 - 피로도

 

접근 방법

처음에는 가장 이상적인 방법을 찾는 그리디 문제인 줄 알았다.

하지만 앞의 선택이 이후의 선택에 영향을 주면 안되는 그리디의 특성을 "남은 피도로"와 "최소 요구 피로도"가 만족 시키지 않아 완전 탐색 방법으로 풀었다.
(던전의 개수도 최대 8개이므로 시간복잡도에서도 문제가 없을 듯 싶었다.)

모든 던전의 순열을 구한 뒤, 각 던전의 탐험 횟수를 담아 max값을 출력하는 방식으로 진행하였다.

exploredCntArr = 각 조합마다 탐험횟수를 담는 배열
dungeonPermutations = 던전의 모든 순열 경우의 수를 담은 2차 배열
exploredCnt = 던전 탐험 횟수(한 던전조합이 끝나면 매번 0으로 초기화)
remainedPirodo = 남은 피로도 (한 던전조합이  끝나면 매번 k로 초기화)
hadPirodo = 입장시 최소 필요한 피로도
usedPirodo = 입장시 사용되는 피로도

function solution(k, dungeons) {
    var answer = 0;
    const exploredCntArr = [];
    const dungeonPermutations = getPermutations(dungeons, dungeons.length)
    
    dungeonPermutations.forEach(dungeon => {
      let exploredCnt = 0;
      let remainedPirodo = k;
      dungeon.forEach((pirodo) => {
        const [hadPirodo, usedPirodo] = pirodo;
            if(remainedPirodo >= hadPirodo){
                remainedPirodo -= usedPirodo;
                exploredCnt++;
            }
        })  
        exploredCntArr.push(exploredCnt);
    })
    
    answer = Math.max(...exploredCntArr);
    
    return answer;
}



const getPermutations= function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]);

  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((permutation) => [fixed, ...permutation]);
    results.push(...attached);
  });

  return results;
};