[프로그래머스] 위클리 챌린지 12주차 (javascript)

문제 ❓

위클리 챌린지 12주차

풀이 방법

문제를 살펴보면 dungeons의 길이가 8로 매우 짧기 때문에 DFS를 통한 완전탐색으로 문제를 해결할 수 있다.

1. 카운트, 현재 피로도, 던전, 결과 배열을 매개 변수로 받는 함수 DFS를 선언한다
2. 카운트가 0 이상일 때 결과배열에 저장
3. 던전의 길이만큼 반복문을 진행하며 현재 피로도가 최소 피로도보다 클 경우 현재 값을 제외한 던전 목록을 추가하여 DFS함수를 다시한번 호출한다.
4. 함수를 통해 반환된 값을 내림차순으로 정렬한 뒤 첫번째 값을 반환한다.

코드

function solution(k, dungeons) {
    const result = dfs(0, k, dungeons, new Set());
        
    return result.sort((a, b) => b - a)[0];
}

const dfs = (cnt, k, dungeons, result) => {
    if (cnt > 0) result.add(cnt);
    
    for (let i = 0; i < dungeons.length; i++) {
        const [min, consume] = dungeons[i];
        
        if (k >= min) {
            // 현재 값을 추출한 배열을 매개변수로 넘김
            const arr = [...dungeons];
            arr.splice(i, 1);
            dfs(cnt + 1, k - consume, arr, result);
        }
    }
    
    return [...result];
}

총평

항상 문제를 풀기전 매개변수의 크기를 체크하여 어떤 알고리즘을 적용해야할지 미리 생각하고 적용한다.
(풀이시간: 5분)