[프로그래머스] 피로도

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 

이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. 

"최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 

예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

 

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

 

입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

 

입출력 예 설명

현재 피로도는 80입니다.

 

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

 

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

 

풀이

처음 시도할 때 예전에 잠깐 보았던 heap 구현방법 중 배열안에 요소를 교환하는 방식을 사용하여 풀어보려고 했으나 응용력이 부족하여 에러만 나고 해결되지 않았다.

그 다음으로는 배열의 길이는 신경쓰지않고 예시처럼 3자리일 경우 원하는 결과를 만들게끔 첫번째부터 기준을 잡고 순회, 계산하는 과정으로 예시문제는 통과했으나, 정확성 테스트의 결과는 처참하였다.

결국 단순하게 풀어보려고 모든 경우의 수에 해당하는 배열을 만들어 클리어 횟수를 세고, 그 횟수를 배열에 넣어준뒤 최대값을 리턴받는 방법으로 풀었다.

function solution(k, dungeons) {
    let dungeonArr; // 모든 던전의 경로를 거치는 경우의 수 배열
    let count = 0; // 던전 클리어 횟수
    const countArr = []; // 던전 클리어 횟수 배열
    
    // 재귀 함수 시작
    function permute(arr, start, current) {
        // 한사이클 종료시 시작되는 과정
        if (start === arr.length - 1) {
            dungeonArr = arr.slice();
            for (let i = 0; i < arr.length; i++) {
                let [demand, consume] = dungeonArr[i];
                // 현재 피로도가 필요피로도보다 크다면
                if (current >= demand) {
                    current -= consume;
                    count++;
                }
            }
            // 클리어 횟수를 배열에 추가한 뒤 횟수 초기화
            countArr.push(count);
            count = 0;
            return;
        }

        // 배열의 요소를 교환하는 과정
        for (let i = start; i < arr.length; i++) {
            [arr[start], arr[i]] = [arr[i], arr[start]];
            permute(arr, start + 1, k);
            [arr[start], arr[i]] = [arr[i], arr[start]];
            }
    }

    // 재귀함수 호출
    permute(dungeons, 0, k);
    // 최대값 리턴
    return Math.max(...countArr);
}

완전탐색을 요구하는 만큼, 시간복잡도와 공간복잡도는 모두 O(n!)이 되었다.

최적화를 시도해보려 했지만 아직 내 수준에서는 큰 벽을 느꼈고 미래의 나에게 맡기기로 하였다.

 

다른 풀이

비슷하지만 매우 달라보이는 다른 풀이가 있어 참고겸 적어본다.

function solution(k, dungeons) {
    if (dungeons.length <= 0) return 0;

    let maxDungeons = 0;
    for (let i = 0; i < dungeons.length; i++) {
        if (k >= dungeons[i][0]) {
            let n = solution(
                k - dungeons[i][1], 
                dungeons.slice(0, i).concat(dungeons.slice(i + 1))
            );
            if (n + 1 > maxDungeons) {
                maxDungeons = n + 1;
            }

            if (maxDungeons >= dungeons.length) return maxDungeons;
        }
    }

    return maxDungeons;
}

시간복잡도는 O(2^n * n), 공간복잡도는 O(n * 2^n)로 직접 풀이한 과정보다 좀 더 최적화되어있다.