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

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

이 문제의 풀이과정은 이 흐름을 따라가면 된다 !

• BFS를 이용해 x에서 시작해 (x + n), (x * 2), (x * 3)을 큐에 넣으며 탐색한다.
• 정답은 처음으로 y에 도달했을 때의 연산 횟수를 리턴하면 된다.
• 방문한 수를 visited로 기록해서 중복 방문을 방지한다.
  
  

코드

---

1. Python

from collections import deque

def solution(x, y, n):
    visited = set()
    queue = deque([(x, 0)])

    while queue:
        current, count = queue.popleft()
        
        if current == y:
            return count
        
        for next_num in (current + n, current * 2, current * 3):
            if next_num <= y and next_num not in visited:
                visited.add(next_num)
                queue.append((next_num, count + 1))
    
    return -1

2. JS

function solution(x, y, n) {
    let visited = new Set();
    const q = [[x, 0]];
    let head = 0;
               
    while(head < q.length){
        const [cur, cnt] = q[head++];
        
        if(cur === y) return cnt;
            
        const nextNums = [cur + n, cur * 2, cur * 3];
        for(const next of nextNums){
            if(next <= y && !visited.has(next)){
                visited.add(next);
                q.push([next, cnt + 1]);
            }
        }
    }
    return -1;
}

결과

---