[프로그래머스] 피로도 (LV2 - JavaScript)

1. 문제

 

제한사항

입출력 예

입출력 예 설명

 

2. 정답 풀이

풀이 전략

• 깊이 우선 탐색 (Depth-First Search) 사용
• 던전을 탐험했는지 확인하기 위한 hash 배열 사용
• 재귀 함수 호출을 통해 던전 입장 순서별로 탐험 가능한 최대 던전 수를 계산
• Math.max 메서드로 재귀 함수 결과 중 최대 값을 return

function solution(k, dungeons) {
    const hash = Array.from({length: dungeons.length}, () => 0);
    let answer = 0;
    
    // 깊이 우선탐색(Depth-First-Search)
    const dfs = (k, cnt) => {
        for(let i=0; i<dungeons.length; i++) {
            // hash를 순회하며 값이 0 && 현재 피로도가 필요 피로도 이상인 경우 던전 방문 
            if (hash[i] < 1 && k >= dungeons[i][0]) {
                hash[i] = 1;
                // 피로도를 소모 & 던전 카운트 증가 후 재귀 호출
                dfs(k - dungeons[i][1], cnt+1);
                hash[i] = 0;
            }
        }
        answer = Math.max(answer, cnt);
        return answer
    }
    
    return dfs(k, 0);
}

 

3. 의문점

const hash = Array.from({length: dungeons.length}, () => 0);

const hash = new Array(dungeons.length).fill(0);

 

문제를 풀고 나서 첫 번째 코드보다 두 번째 코드가 좀 더 직관적인 것 같아서 수정 후 어떤게 더 시간 복잡도가 낮은지 실행해 보았다.

 

Array.from

 

new Array

 

큰 차이는 없지만 Array.from이 조금 빨랐다.

궁금한 마음에 찾아보다가 벤치마킹 사이트가 있어서 실행해봤다. 결과는 new Array의 압도적 승리...😅😅

 

혹시나 벤치마킹 사이트가 이상한지 몰라 직접 확인해봐도 결과는 new Array가 더 빠르다..

 

 

이번 문제는 풀이 과정에서 보다 풀고 난후 생긴 궁금증에서 더 많은 것을 얻은 것 같다. 지금까지 시간 복잡도를 고려한다고 하면서 성능 측정을 따로 해본적은 없는데, 콘솔에 직접 실행 시간도 측정해보고 검색도 많이 해보고 좋은 경험이 된 것 같다.

 

Array.from의 실행 시간이 더 짧게 나온 것은 아직도 궁금증을 해결하지 못했다.

new Array와 Array.from의 시간 복잡도는 조금 더 깊게 찾아봐야겠다...🤔🤔

 

 

 

[프로그래머스] 의상 (LV2 - Javascript)

 

[프로그래머스] 기능개발 (LV2 - JavaScript)