[프로그래머스] 완전탐색 - 피로도 문제 풀이(feat.JS)

오늘은 프로그래머스에서 완전탐색 문제 중 피로도 문제 풀이를 JavaScript로 진행해보려고 합니다. 완전탐색은 알고리즘이 정말 무식해보일정도로 모든 상황을 다 확인해야하지만 어떻게 구현하느냐에 따라 효율적인 해결책을 찾을 수 있을 것이라 생각합니다. 이번 피로도 문제 풀이도 정말 효율적인 해결책을 찾기 위해 재미있게 문제 풀이 시작해보겠습니다.

 

 

프로그래머스 > 완전탐색 > 피로도 문제 풀이

 

 

 

 

＄ 문제 정보

• 문제명: 피로도
• 문제 난이도: Level 2
• 문제 푼 사람 수: 3681명
• 사용 가능 언어: 8개 (JavaScript 사용)

 

 

 

＄ 문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

 

이 문제를 봤을 때, 던전 앤 파이터 게임에서 던전을 들어갈 때 피로도가 소모되는 것으로 기억하는데 그 시스템으로 문제가 만들어진 것이 아닌가 생각이 들 정도로 비슷한 생각이 들었습니다. 이 때, 최소 필요 피로도도 있었나?! 라는 생각과 함께 문제 이해를 쉽게 할 수 있었습니다. 그럼 문제 설명에 대한 정리를 해보겠습니다.

 

 

• 유저가 최대한 많은 던전을 탐험할 수 있는 던전 수 구하기
• Inputs
  • k: 현재 유저의 피로도
  • dungeons: 각 던전별 정보가 담긴 2차원 배열(던전 정보: [최소 필요 피로도, 소모 피로도])
• Output: 현재 유저 피로도(k)로 각 던전을 탐험할 수 있는 최대 던전 수

 

 

 

 

＄ 제한 사항

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

 

 

• 1 ≤ 유저의 현재 피로도 ≤ 5,000
• 1 ≤ 던전(dungeons)의 개수(N) ≤ 8
  • 던전(dungeons) 정보의 길이 = 2
  • 각 던전 정보 = [최소 필요 피로도, 소모 피로도]
  • 최소 필요 피로도 ≥ 소모 피로도
  • 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입니다.

 

 

 

 

＄ 알고리즘 만들기

1. 현재 탐험한 던전을 체크하는 변수(checked)를 만든다.
2. 던전을 순서대로 입장하여 가장 많은 던전을 돌았을 때의 수를 찾을 수 있도록 완전탐색(DFS)을 한다.
3. 완전탐색을 통해 얻은 최대로 많은 던전을 돌았을 때의 결과를 반환한다.

 

 

이번 문제의 키포인트는 모든 순서를 탐색하여 가장 많은 던전을 탐험했을 때의 수를 찾기 위한 알고리즘인 완전탐색(DFS) 알고리즘을 활용한 것입니다. 그럼 DFS 알고리즘을 활용하여 코드 구현을 해보겠습니다.

 

 

 

 

＄ 코드 구현

function solution(k, dungeons) {
    var answer = -1;
    // 1. 현재 탐험한 던전을 체크하는 변수(checked)를 만든다.
    const checked = new Array(dungeons.length).fill(false);

    // 2. 던전을 순서대로 입장하여 
    //    가장 많은 던전을 돌았을 때의 수를 찾을 수 있도록 
    //    완전탐색(DFS)을 한다.
    enterDungeuns(k);

    function enterDungeuns(k, count = 0) {
        for (let i = 0; i < dungeons.length; i++) {
            if (!checked[i] && k >= dungeons[i][0]) {
                checked[i] = true;
                enterDungeuns(k - dungeons[i][1], count + 1);
                checked[i] = false;
            }
        }
        answer = answer < count ? count : answer;
    }
    
    // 3. 완전탐색을 통해 얻은 최대로 많은 던전을 돌았을 때의 결과를 반환한다.
    return answer;
}

 

 

 

 

＄ 채점 결과

 

 

이번 피로도 문제 풀이 채점 결과 정확성 테스트 케이스 19개를 모두 통과하여 문제 풀이를 완료하였습니다.