프로그래머스 [피로도] - 구현 Lv.2

구현

• 완전 탐색을 이용하여 해당 문제에서 제시한 조건에 걸맞는 답을 도출해야하는 문제이다.

아이디어 실수

• 최대한 많은 경우의 수를 고려해야 한다는 지문을 보고, 그리디 알고리즘으로 착각했다.
• 그래서 입장 조건 피로도와 소모 피로도의 차이가 가장 큰 순서대로 정렬 후, 차례대로 방문하여 방문 횟수를 반환하였다.
• 테스트 케이스 9, 12, 13이 통과하지 못했다.

입출력 조건

• 입출력 조건을 보면, 최대 던전의 갯수는 8개로 매우 적다.
• 즉 완전 탐색을 요구하는 문제이다.
• 따라서 나올 수 있는 모든 던전들의 순열 경우의 수를 한 배열에 보관하고
• 이 목록들에 대해 전부 방문 횟수를 계산하여 최대값을 반환하였다.

최종 코드

function solution(k, dungeons) {
    // 던전의 갯수는 최대 8개 이므로, 8개 모두의 경우의 수를 구해야한다.
    // 1. 8!로 순열로 줄 세우기
    // 2. 줄세운 목록들 전부 탐색
    // 3. 탐색 후 방문한 던전의 수를 모으고
    // 4. 이 중 최대값을 반환하기
    function permutations(arr, n) {
  // 1개만 뽑는다면 그대로 순열을 반환한다. 탈출 조건으로도 사용된다.
  if (n === 1) return arr.map((v) => [v]);
  let result = [];

  // 요소를 순환한다
  arr.forEach((fixed, idx, arr) => {
    // 현재 index를 제외한 요소를 추출한다.
    // index번째는 선택된 요소
    const rest = arr.filter((_, index) => index !== idx);
    // 선택된 요소를 제외하고 재귀 호출한다.
    const perms = permutations(rest, n - 1);
    // 선택된 요소와 재귀 호출을 통해 구한 순열을 합쳐준다.
    const combine = perms.map((v) => [fixed, ...v]);
    // 결과 값을 추가한다.
    result.push(...combine);
  });

  // 결과 반환
  return result;
}
        const arr = permutations(dungeons, dungeons.length)
        const answer = []
        let kCopy = k
    while(arr.length > 0) {
        // 탐색할 던전 목록
       const dgList = arr.shift()
       // 던전 목록 탐색 전 피로도 초기화
       let kCopy = k
       // 던전 목록 탐색 전 방문 횟수 초기화
       let count = 0
       // 던전 목록 내 순회하여 탐색 횟수 측정 후 answer에 push하기
       while(1) {
           if(dgList.length > 0) {
                const visit = dgList.shift()
                if(kCopy < visit[0]) {
                    answer.push(count)
                    break;
                }    
               kCopy = kCopy - visit[1]
               count += 1
           } else {
               answer.push(count)
               break;
           }

       }
    }
    return Math.max(...answer)
}