프로그래머스 코딩테스트 연습 Level 2 - 피로도 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 피로도 (JavaScript)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중 완전탐색, 깊이 우선 탐색(DFS) 관련 문제인,

[피로도] 문제를 JavaScript를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

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입니다.

 

 

작성한 답

solution.js

function solution(k, dungeons) {
    let answer = 0;
    const ch = Array.from({ length: dungeons.length }, _ => 0);
    
    const dfs = (fatigue, depth) => {
        answer = Math.max(answer, depth);
        
        for(const i in dungeons) {
            const [need, consume] = dungeons[i];
            if(!ch[i] && fatigue >= need) {
                ch[i] = 1;
                dfs(fatigue - consume, depth + 1);
                ch[i] = 0;
            }
        }
    }
    
    dfs(k, 0);
    
    return answer;
}

 

설명

주어지는 모든 던전들을 돌아보면서 가장 많이 던전을 돌 수 있는 방법을 알아야 하므로 DFS 를 바로 떠올릴 수 있다면 사용하면 문제를 해결할 수 있습니다!

 

이미 방문했던 던전을 체크해둘 ch 배열을 던전의 개수만큼 0 으로 초기화 해준 뒤,

dfs를 통해 모든 과정으로 던전들을 방문하기 시작합니다.

모든 던전들에 대해 이미 방문하지 않았으면서 현재의 피로도가 해당 던전을 방문하는데 필요시되는 "최소 필요 피로도" 보다 크거나 같다면 해당 던전을 또 방문하면서 소모되는 피로도를 빼주고 방문한 던전의 개수를 1씩 증가시키면서 ch 배열에는 해당 던전의 index는 방문했다는 표시로 1을 표기해둡니다.

던전들을 하나씩 방문하면서 이제껏 했던 과정중에서 가장 많이 방문한 값인지 answer에 계속 최대값을 넣어줍니다.

 

모든 과정을 통해 던전을 돌았으면 answer에는 가장 많이 던전을 돌 수 있는 방법의 던전을 방문한 횟수가 들어있을 것이고 해당 값을 반환하는 것으로 문제를 해결할 수 있습니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.