프로그래머스 level 2 - 숫자 변환하기(Javascript)

숫자 변환하기

풀이과정

• 처음 시도에서는 단순히 bfs를 통해 x -> y로 만드는 최소 count를 찾으려 했다.
  • num > y 인 경우만 예외처리 했지만 불충분 했음
• 두 번째 시도에서는 checked 배열을 통해 체크한 적이 있는 숫자는 큐에 넣지 않도록 수정함
  • 불충분…
• 세번째 시도에서는 x -> y가 아닌 y -> x를 만드는 방법을 구현했다.
  • 2와 3으로 나눠서 나오는 수가 정수가 아니라면 큐에 담기지 못하기 때문에 경우의 수가 확 줄어들게 된다.

첫번째 시도(시간초과)

function solution(x, y, n) {
    var answer = 0;
    
    function bfs(x){
        const q = [[x, 0]];
        while(q.length){
            const [num, count] = q.shift();
            if(num > y) continue;
            if(num === y) return count;
            q.push([num + n, count + 1]);
            q.push([num * 2, count + 1]);
            q.push([num * 3, count + 1]);
        }
        return -1;
    }
    
    answer = bfs(x);
    
    return answer;
}

두번째 시도(시간초과)

function solution(x, y, n) {
    var answer = 0;
    const checked = [...Array(y)].map(v=>false);
    
    
    function bfs(x){
        const q = [[x, 0]];
        while(q.length){
            const [num, count] = q.shift();
            if(num > y) continue;
            if(num === y) return count;
            checked[num] = true;
            if(num + n <= y && !checked[num + n]) q.push([num + n, count + 1]);
            if(num * 2 <= y && !checked[num * 2]) q.push([num * 2, count + 1]);
            if(num * 3 <= y && !checked[num * 3]) q.push([num * 3, count + 1]);   
        }
        return -1;
    }
    
    answer = bfs(x);
    
    return answer;
}

세번째 시도

function solution(x, y, n) {
    var answer = 0;
    const checked = [...Array(y)].map(v=>false);
    
    function bfs(){
        const q = [[y, 0]];
        while(q.length){
            const [num, count] = q.shift();
            if(num < x) continue;
            if(num === x) return count;
            checked[num] = true;
            if(num - n >= x && !checked[num - n]) 
	            q.push([num - n, count + 1]);
            if(num / 2 >= x && num % 2 === 0 && !checked[num / 2])
	            q.push([num / 2, count + 1]);
            if(num / 3 >= x && num % 3 === 0 && !checked[num / 3]) 
	            q.push([num / 3, count + 1]);
        }
        return -1;
    }
    
    answer = bfs(x);
    
    return answer;
}