문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한 사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

풀이

아이디어

• 문제를 읽고 조금 안되서 x가 출발지고 y가 도착지인 경로를 찾는 BFS 문제구나! 했다. (당연히 visited와 queue를 두었다. 그런데 여기서 visited는 계산 결과가 중복되는 것을 방지하기 위해서 Set으로 가져가기로 했다.)
• 그런데 BFS로 풀었는데 시간 초과가 발생했다. 조금 찾아보니 자바스크립트가 완전한 큐를 지원하지 않기 때문에 Array.prototype.shift() 연산에서 시간 초과가 걸리는 것 같았다.
• 그래서 shift 연산을 최대한 쓰지 않으려고 생각한 결과, 큐의 인덱스(qIdx)라는 변수를 두고 queue.shift() 대신 qIdx++을 해줘서 앞에거를 제외시키는 효과를 주었다!!
• 또한, 큐의 원소 각각에 계산을 몇 번 해서 얻어진 결과인지를 표시하는 정보도 같이 넣어 객체로써 저장했다.

시간 초과 코드

function solution(x, y, n) {
    var answer = 0;
    var queue = [{value: x, iter: 0}];
    var visited = new Set([x]);
    
    if(x == y) return 0;
    
    while(queue.length) {
        const val = queue.shift();
        if(val.value === y) {
            answer = val.iter;
            break;
        }
        const temps = [val.value + n, val.value * 2, val.value * 3].filter(v => v <= y && !visited.has(v));
        temps.forEach(t => {queue.push({value: t, iter: val.iter + 1}); visited.add(t)});
    }
    
    if(answer == 0) return -1;
    return answer;
}

맞은 코드

function solution(x, y, n) {
    var answer = 0;
    var queue = [{value: x, iter: 0}];
    var visited = new Set([x]);
    var qIdx = 0;
    
    if(x == y) return 0;
    
    while(qIdx <= queue.length - 1 && queue[qIdx].value <= y) {
        const val = queue[qIdx++];
        if(val.value === y) {
            answer = val.iter;
            break;
        }
        const temps = [val.value + n, val.value * 2, val.value * 3].filter(v => v <= y && !visited.has(v));
        temps.forEach(t => {queue.push({value: t, iter: val.iter + 1}); visited.add(t)});
    }
    
    if(answer == 0) return -1;
    return answer;
}

돌아보기

💡Array.prototype.shift() 때문에 시간 초과 터지는 것 같다면 지금처럼 queue의 index를 활용한 트릭을 이용해보자!!