백준 / 그래프 / 9019번 / DSLR / JS

문제 간단설명

네 자리 숫자 A를 B로 바꾸기 위해 아래 4개의 명령어를 사용해야 합니다.

• D: A를 두 배로 만들고, 10000 이상이면 10000으로 나눈 나머지.
• S: A에서 1을 뺀 값. 0이면 9999.
• L: A의 왼쪽 회전. 예: 1234 → 2341.
• R: A의 오른쪽 회전. 예: 1234 → 4123.

목표:

• 숫자 A에서 시작해 숫자 B로 바꾸는 최소한의 명령어 나열을 구하시오.
• 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

 

 

제한 사항

• A 와 B는 모두 0 이상 10,000 미만이다.

 

실패 코드 (시간 초과)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

let index = 0;
const T = +input.shift();

function solution() {
  for (let testCase = 1; testCase <= T; testCase++) {
    const [A, B] = input[index++].split(' ').map(Number);

    bfs(A, B);
  }
}

function bfs(A, B) {
  const queue = [[A, '']];
  const visited = Array.from({ length: 10000 }, () => false);

  visited[A] = true;

  let head = 0;
  while (queue.length > 0) {
    const [curNumber, totalCommand] = queue[head++];

    if (curNumber === B) {
      console.log(totalCommand);
      return;
    }

    const nextNumberList = [
      [D(curNumber), 'D'],
      [S(curNumber), 'S'],
      [L(curNumber), 'L'],
      [R(curNumber), 'R'],
    ];
    nextNumberList.forEach(([nextNumber, command]) => {
      if (visited[nextNumber]) {
        return;
      }

      visited[nextNumber] = true;
      queue.push([nextNumber, totalCommand + command]);
    });
  }
}

function D(number) {
  return (number * 2) % 10000;
}

function S(number) {
  return number - 1 === 0 ? 9999 : number - 1;
}

function L(number) {
  const strNumber = number.toString().padStart(4, '0');
  return Number(strNumber.slice(1) + strNumber[0]);
}

function R(number) {
  const strNumber = number.toString().padStart(4, '0');
  return Number(strNumber[3] + strNumber.slice(0, 3));
}

solution();

 

문제 그대로 구현하였는데, 계속 시간 초과가 나왔다. AI에게 도움 요청을해서 로직에 대한것만 확인해달라고 하였지만 로직에 대한것은 틀린것이 없었다.

아무리봐도 BFS 과정에선 틀린것이 없을 것 같아서, 함수로 눈길을 돌렸다.

L과 R 함수에 padStart(), slice() 같은 함수가 있어서 만약 L,R 커맨드를 많이 하게 될 경우 시간초과가 날 것 같았다.

 

성공 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

const T = +input.shift();

function solution() {
  for (let testCase = 1; testCase <= T; testCase++) {
    const [A, B] = input.shift().split(' ').map(Number);

    bfs(A, B);
  }
}

function bfs(A, B) {
  const queue = [[A, '']];
  const visited = Array(10000).fill(false);
  visited[A] = true;

  while (queue.length > 0) {
    const [cur, commandList] = queue.shift();

    if (cur === B) {
      console.log(commandList);
      return;
    }

    const nextStateList = [
      [D(cur), 'D'],
      [S(cur), 'S'],
      [L(cur), 'L'],
      [R(cur), 'R'],
    ];

    for (const [nextNumber, command] of nextStateList) {
      if (!visited[nextNumber]) {
        visited[nextNumber] = true;
        queue.push([nextNumber, commandList + command]);
      }
    }
  }
}

function D(number) {
  return (number * 2) % 10000;
}

function S(number) {
  return number === 0 ? 9999 : number - 1;
}

function L(number) {
  const d1 = Math.floor(number / 1000);
  return (number % 1000) * 10 + d1;
}

function R(number) {
  const d4 = number % 10;
  return Math.floor(number / 10) + d4 * 1000;
}

solution();

 

생각했던게 맞았다. L과 R함수의 메서드 사용에 대한 시간복잡도가 문제였다.

다른건 바뀐게 없지만, 본래 String으로 형변환하여 한칸씩 옮기는것을 처리했던 것을 단순히 모듈러 연산을통해 자릿수를 조정하여 처리하였다.

특별한 메서드 없이 단순 연산이기 때문에 시간복잡도가 줄었을 것이고, 통과하였다.