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

📖 문제

level2 숫자 변환하기

✏️ 나의 풀이

문제를 보자마다 일단 배열에 넣어서 해보자! 이런 생각이 들었다.

배열에 넣는 과정에서 현재 몇번째 연산을 했는지도 필요하기에 [value, cnt] 형식으로 배열에 넣었다.

다음으로 연산을 하고 난 후 push 메소드를 사용할 것이므로 0번째 인덱스의 값을 가져와 다시 연산을 시켜줘야 할 것같았다.

이렇게 생각하니 BFS 알고리즘을 통해 풀 수 있는 문제라고 확신이 들었다.

if(x === y) return 0;
const queue = [[x, 0]];
const visited = new Array(1000000).fill(false);
let index = 0;

• 우선 x와 y가 동일할 경우 연산할 필요가 없으므로 0을 반환해준다.
• queue: BFS에서 사용하는 queue로 배열이다.
• visited: 같은 값을 검사할 필요가 없으므로 이를 방지하기 위한 배열이다.
• index: shift연산자를 이용해 0번째 인덱스 값을 가져오면 시간초과가 발생하기에 index로 접근한다.

while(queue.length > index){
    const [value, cnt] = queue[index];
    const temp = [];
    temp.push(value + n);
    temp.push(value * 2);
    temp.push(value * 3);
    ...
}

• 만일 queue의 길이가 index보다 작다면 queue는 비어있는 것과 동일하기 때문에 index가 queue보다 작을경우에만 반복문을 돌린다.
• temp: 연산 후 해당 값을 검사하기 이전에 잠시 담아둘 배열이다.

while(queue.length > index){
    ...
    for(let i = 0; i < temp.length; i++){
        if(temp[i] === y) return cnt + 1;
        if(visited[temp[i]] || temp[i] > y) continue;
        
        visited[temp[i]] = true;;
        queue.push([temp[i], cnt + 1])
    }
    index += 1;
}

• for(): temp 안에 있는 값들을 검사하기 위한 배열이다.
• temp[i]===y: 연산된 값이 y와 같다면 최소 연산 횟수를 얻은 것이므로 cnt에 1을 더해 반환한다.
• 검사한 이력이 있거나 연산한 값이 y보다 더 크다면 더 이상 검사할 필요가 없으므로 continue 구문을 만난다.
• 현재 값을 토대로 visited 배열을 업데이트 시켜준다.
• queue에 현재 값과 cnt에 1을 더해 배열 형태로 넣어준다.

👩‍💻 코드

function solution(x, y, n) {
    if(x === y) return 0;
    var answer = 0;
    const queue = [[x, 0]];
    const visited = new Array(1000000).fill(false);
    let index = 0;
    visited[x] = true;
    while(queue.length > index){
        const [value, cnt] = queue[index];
        const temp = [];
        temp.push(value + n);
        temp.push(value * 2);
        temp.push(value * 3);
        for(let i = 0; i < temp.length; i++){
            if(temp[i] === y) return cnt + 1;
            if(visited[temp[i]] || temp[i] > y) continue;
            
            visited[temp[i]] = true;;
            queue.push([temp[i], cnt + 1])
        }
        index += 1;
    }
    return -1;
}