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

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

프로그래머스

---

1) 풀이

이것도 꽤 시간이 걸린 문제....

사실 푸는 방법은 단순하게 생각해서 풀 수는 있는데

시간초과가 자꾸 나서.. 방법이 뭔지 모르겠어서 ... 한참을 고민했다

그래서 질문하기도 찾아보고, 여러 블로그에서 다른 분들 푸는 방법을 봤는데

일단..dp로 푸는 방법이 있었다

 

근데 일단 내가 dp에 대해 아직 서툴기도 하고 해서 내가 그나마 자신있는 bfs 방식으로 하기로 했다!

근데 이제 시간초과가 안 나는 것을 곁들인...

여러 자료를 참고하면서 +n, *2. *3 대신-n, /2, /3을 하는 것이 더 효율적이라는 것을 깨달았다

즉 x에서 bfs 를 시작하는 것이 아니라 y부터 거꾸로 내려가는 것인데

그 이유는

x부터 시작해서 +n, *2. *3 를 하는 건 무조건 정수로 나오기 때문에 시간이 오래 걸리는데

그 반대는 정수가 아니게 나올 확률이 있기 때문에 정수가 아닌 경우 걸러낼 수 있어서 효율적! 

이렇게 해서.. 이 문제를 풀었다 자그마치 3일에 걸려 푼 문제..

2) 최종 소스코드

function solution(x, y, n) {
    const q=[];
    q.push([y,0]);
    while(q.length>0){
        let cur=q.shift();
        if(cur[0]===x) {
          return cur[1];
        }
        if(cur[0]-n>x&&(cur[0]-n)%1===0) {
            q.push([cur[0]-n,cur[1]+1]);
        }else if(cur[0]-n===x) return cur[1]+1;
        if(cur[0]%2===0&&cur[0]/2>x){ 
            q.push([cur[0]/2,cur[1]+1]);
        }else if(cur[0]/2===x) return cur[1]+1;
        if(cur[0]%3===0&&cur[0]/3>x) {
            q.push([cur[0]/3,cur[1]+1]);
        }else if(cur[0]/3===x) return cur[1]+1;
          
    }
    return -1;
}