문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

1. 2를 곱한다.
2. 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력

2 162

예제 출력

5

내가 했던 풀이 방법

1. queue에 [A, 0]을 담아준다. 이때 A는 문자열이다. 추후 오른쪽에 1을 붙여줘야 하기때문에 String으로 두는 것이 더 편하다. 0은 count 값이다. (마지막 출력에서 1을 더한 값을 출력하므로 1로 두면 더 계산이 편할 수도?)
2. count는 -1로 둔다. 만들 수 없는 경우에는 해당 값이 변하지 않으므로 -1로 두어 편하게 계산할 수 있다.
3. queue의 length가 없어질 때까지 BFS 연산을 한다. 맨 앞에 있는 요소를 제거해주고 해당 요소 값 중 number 값이 B와 같다면 count를 해당 count로 저장해주고 반복문을 탈출한다. (BigInt를 쓰긴 했으나 BigInt는 이후 연산과정에서 넘어갈 가능성이 있지, 이 부분에서는 없을 것 같으므로 생략해도 될 것 같다.)
4. 해당 number의 2배한 값이 B보다 작거나 같다면 해당 값을 문자열로 변환해준 값과 count+1을 배열로 담아 queue에 담아준다. 1을 수의 오른쪽에 붙여주었을 때도 B보다 작거나 같다면 같은 방법으로 queue에 담아준다.
5. 모든 연산이 끝난 뒤에 count 값을 출력한다.

코드

const fs = require('fs');
let n = fs.readFileSync(0, 'utf-8').toString().trim();

let [A, B] = n.trim().split(' ');

let queue = [];
queue.push([A, 0]);

let count = -1;
let calculate = 0;
while (queue.length) {
  let number = queue.shift();

  if (BigInt(number[0]) === BigInt(B)) {
    count = number[1];
    break;
  }

  if (BigInt(number[0]) * 2n <= BigInt(B)) {
    calculate = Number(number[0]) * 2;
    queue.push([calculate.toString(), number[1] + 1]);
  }
  if (BigInt(number[0] + 1) <= BigInt(B)) {
    calculate = Number(number[0] + 1);
    queue.push([calculate.toString(), number[1] + 1]);
  }
}

console.log(count !== -1 ? count + 1 : count);

회고

연산 횟수를 줄이려고 계산된 결과들을 담아뒀는데 메모리 초과가 발생했다. 처음에는 B 크기만큼으로 두었는데 생각해보니 B가 10^9까지 가능한 걸 감안하면 말도 안 되는 짓이었다. 그래서 해당 값을 방문하지 않으면 false, 이게 아니고 방문하면 배열에 담는 걸로도 수정했는데 이전보다는 아니였지만 여전히 메모리 초과가 발생했다. 마지막으로 Set으로 수정해줘서 해결했는데, Set에 해당 값을 담아주는 걸 까먹었는데도 정답인 걸 보니 굳이 연산횟수를 줄이려고 하지 않아도 해결되는구나 싶어서 관련 코드는 지웠다. 한 번에 맞출 수 있었는데 아쉽구만.