프로그래머스 코딩테스트 풀이(js) > 숫자 변환하기 (lv2)

 

문제🔽

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

다른사람 풀이 🔽

function solution(x, y, n) {
  if (x === y) return 0;
  const dp = {};
  dp[x] = 0;
  let data = [x];
  while (data.length) {
    const newData = [];
    for (const d of data) {
      for (const e of [d + n, d * 2, d * 3]) {
        if (e > y || dp[e]) continue;
        if (e === y) return dp[d] + 1;
        dp[e] = dp[d] + 1;
        newData.push(e);
      }
    }
    data = newData;
  }
  return -1;
}

내풀이🔽

1. 첫시도 실패 ❌ -> 런타임 에러(시간 초과)

function solution(x, y, n) {
    var answer = 0;
    const countList = []
    const dfs = (x,count)=>{        
        if(x==y){
            countList.push(count)
            return 
        }if(x>y){
            return 
        }
        dfs(x+n,count+1)
        dfs(x*2,count+1)
        dfs(x*3,count+1)
    }
        dfs(x,0)

    if(countList.length){
        answer=Math.min(...countList)    
    }else{
        answer = -1;
    }
    return answer;
}

🔽 아래와 같이 에러가 뜸 

2. 두번째 시도 > 💯 성공

function solution(x, y, n) {

    if(x===y){
        return 0;
    }else if(x>y){
        return -1;
    }
    
    let countArray = Array(y+1).fill(Infinity)
    countArray[x] = 0;
    
    for(i=x+1; i<y+1; ++i){
        if(i-n>=x){
            countArray[i] = Math.min(countArray[i],countArray[i-n]+1)
        }
        if(i%2===0&&i/2>=x){
            countArray[i] = Math.min(countArray[i],countArray[i/2]+1)         
        }
        if(i%3===0&&i/3>=x){
            countArray[i] = Math.min(countArray[i],countArray[i/3]+1)         
        }
    }
    return countArray[y]===Infinity? -1:countArray[y]
}

 

느낀점😮 

처음으로 DFS ( Depth first search ) 라는 개념을 접할 수 있는 문제였다. DFS/BFS 이런 용어들이 있는데 용어는 몰라도 되고 그 개념을 체득하면 될 것 같다. 2번째 code 작성 시 > 다른사람의 code를 참고하여 작성 하였는데 해당과 같은 알고리즘을 푼 적이 없어서 온전히 이해하는데 오래 걸렸다.