[프로그래머스] 숫자 변환하기 문제 풀이

🔥문제 요약

1. 자연수(0보다 큰 정수) x에서 시작해서 y로 바꾸고 싶습니다.
2. 사용할 수 있는 연산은❓
• x에 n을 더하기
• x에 2를 곱하기
• x에 3을 곱하기
3. 최소한의 연산으로 x를 y로 만드는 횟수를 계산합니다.
4. x를 y로 만들 수 없다면 -1을 반환🔁

🤔문제 푸는 방법

숫자 변환하려면 계산을 해보면서 가능한 숫자를 하나씩 찾아야 함
🛠사용할 도구 : 큐 [Queue]

• 큐➡앞에서부터 하나씩 꺼내서 처리하는 방식으로 동작
• 새로 만들어지는 숫자는 큐의 끝에 계속 추가됨

👩‍💻코딩

function solution(x, y, n) {
  // 1. 변환을 시작하는 숫자 x를 넣고 연산 횟수를 0으로 초기화
  let queue = [[x, 0]];  // queue = [[현재 숫자, 연산 횟수]]
  
  // 2. 방문했던 숫자를 기록할 공간을 만듦
  // 이미 방문한 숫자는 다시 안 감
  let visited = new Set();
  visited.add(x);  // 시작 숫자 x는 이미 방문했으니까 기록
  
  // 3. 큐가 빌 때까지 반복 (모든 숫자를 하나씩 검사할 것)
  while (queue.lenght > 0) {
    // 4. 큐의 맨 앞에 있는 숫자를 꺼냄
    // current = 지금 숫자, count = 연산 횟수
    // shift: JS 배열에서 맨 앞에 있는 요소 꺼내는 메서드
    // 👉 맨 앞의 [10, 0]이 꺼내짐
    let [current, count] = queue.shift();
    
    // 5. 만약 현재 숫자가 목표 숫자 y라면, 끝! 연산 횟수를 반환
    if (current === y) {
      	return count;
    }
    
    // 6. 현재 숫자에서 세 가지 연산을 해봄
    let nextValues = [current + n, current * 2, current * 3];
    
    // 각각의 새로운 숫자를 확인
    // for ...of : 배열을 순회
    for (let next of nextValues) {
      // 7. 만약 y보다 크거나 이미 방문했던 숫자라면 무시
      if (next > y || visited.has(next)) continue;
      
      // 8. 새로운 숫자를 큐에 추가하고 방문했다고 기록
      queue.push([next, count + 1]);  // 연산횟수 1증가
      visited.add(next);
    }
  }
  // 9. 큐를 다 돌았는데도 y에 도달하지 못했다면 -1반환
  return -1;
}

예제 : x = 10, y = 40, n = 5

1. 처음 숫자 = 10 ➡ 큐 = [[10, 0]]
• 숫자 10에서 가능한 연산 : 10+5=15, 10*2=20, 10*3=30
• 큐 업데이트 : [[15, 1], [20, 1], [30, 1]]
2. 다음 숫자 = 15 ➡ 큐 = [[20, 1], [30, 1]]
• 숫자 15에서 가능한 연산 : 15+5=20, 15*2=30, 15*3=45
• 큐 업데이트 : [[20, 1], [30, 1], [45, 2]]
• x에 3을 곱하기
3. 다음 숫자 = 20 ➡ 목표 숫자 40을 계산할 수 있음❗
• 20*2=40 ➡ 정답 = 2번 연산