[프로그래머스][Javascript]숫자 변환하기

문제

숫자 변환하기

프로그래머스

 

dfs로 푼 코드이다. 

function solution(x, y, n) {
    let r = [];
    function fun(v,l){
        //console.log(v+","+l)
        if(v === y){ r.push(l); return;}
        else if(v > y){
            return 
        }
        fun(v+n,l+1);
        fun(v*2,l+1);
        fun(v*3,l+1);
        return;
    } 
    
    fun(x,0);
    if(!r.length){ return -1;}
    return Math.min(...r);
}

결과..

처참한 결과

 

배열을 이용해서 push, shift를 이용해 큐로도 풀었는데 dfs로 풀었을 때와 같이 시간 초과가 떴다. 

 

 

해결 방법은 DP..!

function solution(x, y, n) {
    var answer = 0;
    let dp = new Array(y+1).fill(Infinity);
    dp[x] = 0; // x가 x가 되기 위해 필요한 연산 수는 0 이다.
    
    for (let i =x;i<=y;i++){
        dp[i + n] = Math.min(dp[i+n],dp[i] + 1); //최단 거리로 계속 업데이트
        dp[i*2] = Math.min(dp[i*2],dp[i] + 1);
        dp[i*3] = Math.min(dp[i*3],dp[i] + 1);
    }
    return dp[y] == Infinity ? -1 : dp[y];
}

각 배열 자리에 x에서 해당 인덱스 자리가 되는데 필요한 최소 연산 수를 업데이트하며 담는다. 

for문에서 i가 구하고자 하는 값인 y까지 가게 되면 x에서 y까지 가기 위한 최소 연산 수가 dp [y]에 담기게 된다. 

 

결과..⭐

 

✅checkpoint!

Math.min(...arr)	배열 안에서의 최솟값을 반환한다.
let dp = new Array(10).fill(Infinity);	Infinity 값으로 채워진 length가 10인 배열을 만든다.
arr.shift()	배열의 첫 번째 요소를 제거하고 제거된 요소를 반환한다.

 

💡idea 요약

dfs	함수(value, level) /재귀함수 구현	시간 초과, 런타임에러
큐	큐 배열을 만들고 for문을 돌리며 배열에 (value,level)을 push함, shift를 사용하여 value값을 확인	시간초과
dp	y+1크기 배열을 만든 후 배열 자리에 x에서 해당 인덱스 자리가 되는데 필요한 최소 연산 수를 업데이트	통과