[백준] 16953번: A → B - Node.js (자바스크립트)

1. 문제 ㅡ 16953번: A → B (난이도: Silver II)

16953번: A → B

2. 풀이 ㅡ Node.js (자바스크립트)

const [A, B] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(val => +val);

const solution = (A, B) => {
  const queue = [[A, 1]];

  while (queue.length) {
    const [current, count] = queue.shift();

    if (current === B) return count;

    const oneAdded = current * 10 + 1;
    const multiplied = current * 2;

    if (oneAdded <= B) queue.push([oneAdded, count + 1]);
    if (multiplied <= B) queue.push([multiplied, count + 1]);
  }

  return -1;
};

console.log(solution(A, B));

2-1. 풀이 설명

주어진 두 개의 연산(곱하기 2 & 가장 오른쪽에 1 추가)만 수행해서 정수 A를 정수 B로 바꾸기까지 걸리는 최소 연산 횟수를 구하면 되는 문제다. BFS로 접근하면 쉽게 풀린다. 

 

A(시작 정수)와 1(누적 연산 횟수)를 queue에 넣고 while문을 돌면서

 

• 현재 queue의 가장 앞에 위치한 A 값이 B와 같다면 1을 반환한다 (Break Point)
• Break 조건에 해당하지 않는다면 현재 정수에 2를 곱한 값(multiplied)과 가장 오른쪽에 1을 붙인 값(oneAdded)을 구한다 
• 두 값 모두 B와 같거나 B보다 작은 경우 count + 1 과 함께 큐에 넣어준다

만약 while문 break point에 의해 값이 반환되지 않은채 while문이 종료되는 경우 A를 B로 변경할 수 없다고 판단하고 -1을 반환하도록 했다.