자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.
x
가 출발지고 y
가 도착지인 경로를 찾는 BFS 문제구나! 했다. (당연히 visited와 queue를 두었다. 그런데 여기서 visited는 계산 결과가 중복되는 것을 방지하기 위해서 Set으로 가져가기로 했다.)Array.prototype.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를 활용한 트릭을 이용해보자!!