[JS] 프로그래머스 / 완전탐색 / 피로도

문제

프로그래머스

정답

// dfs 사용 X

function solution(k, dungeons) {
  let answer = []; // 탐험한 던전들을 저장하는 배열 (탐험 횟수를 세기 위한 용도)

  while (k > 0) { // 현재 피로도가 0보다 큰 동안 반복
    // 각 던전마다 [최소 필요 피로도, 탐험 가능한 던전 수, 던전 인덱스] 배열을 생성
    const choices = dungeons
      .map((dungeon, index) => {
        const [minFatigue, consumeFatigue] = dungeon; // 던전의 최소 필요 피로도와 소모 피로도
        return [
          minFatigue,
          dungeons.filter((_, i) => i !== index && k - consumeFatigue >= _[0]).length, // 현재 던전을 제외하고 탐험할 수 있는 던전의 개수 계산
          index, // 던전의 인덱스
        ];
      })
      .filter(([minFatigue]) => k >= minFatigue); // 현재 피로도보다 작은 최소 필요 피로도를 가진 던전만 남김

    if (choices.length === 0) break; // 탐험 가능한 던전이 없으면 루프 종료

    // 탐험 가능한 던전 중 탐험 후 남은 피로도로 더 많은 던전을 탐험할 수 있는 순서로 정렬
    choices.sort((a, b) => {
      if (a[1] === b[1]) {
        return b[0] - a[0]; // 탐험 가능 개수가 같으면 최소 필요 피로도가 큰 던전을 우선 선택
      } else {
        return b[1] - a[1]; // 탐험 가능 개수가 다르면 탐험 가능 개수가 많은 던전을 우선 선택
      }
    });

    const bestChoiceIndex = choices[0][2]; // 탐험할 던전 중 최선의 선택 인덱스

    k -= dungeons[bestChoiceIndex][1]; // 선택한 던전의 소모 피로도만큼 현재 피로도 감소
    answer.push(dungeons.splice(bestChoiceIndex, 1)); // 탐험한 던전을 dungeons에서 제거하고 answer에 추가
  }

  return answer.length; // 탐험한 던전 개수 반환
}