[백준] DSLR | 자바스크립트 JS | BFS | G4

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

 

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

 

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

 

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

 

풀이 과정

현재 수(current)에 D, S, L, R 명령어를 하나씩 적용해 너비 우선 탐색을 해나가다 target을 만나면 찾는 것을 중단한다. 접근은 문제를 읽고 BFS를 바로 떠올릴만큼 단순했지만 4가지의 명령어로 current를 변형해 다음 탐색할 next에 해당하는 수를 가공하는 것에서 메모리와 시간 소요 정도가 차이가 나 여러 번 시도했다. 

 

제출 코드

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let N, countN;

const solution = ([num, target]) => {
  const visited = new Array(10001).fill(null);
  visited[num] = "";
  const queue = [num];

  const checkNum = (current, next, type) => {
    if (visited[next] === null) {
      queue.push(next);
      visited[next] = visited[current] + type;
    }
  }

  while (queue.length > 0) {
    let current = queue.shift();

    if (current === target) {
      console.log(visited[current]);
      return;
    }

    let D = (current * 2) % 10000;
    checkNum(current, D, 'D');

    let S = current === 0 ? 9999 : current - 1;
    checkNum(current, S, 'S');

    let L = Math.floor(current / 1000) +  (current % 1000) * 10;
    checkNum(current, L, 'L');

    let R = (current % 10) * 1000 + Math.floor(current / 10);
    checkNum(current, R, 'R');
  }
};

readline
  .on("line", (line) => {
    if (!N) {
      N = +line;
      countN = N;
    } else {
      solution(line.split(" ").map(Number));
      countN--;
      if (!countN) {
        readline.close();
      }
    }
  })
  .on("close", () => {
    process.exit();
  });

 

시행착오

1. parseInt의 오용 : L의 네 번째 인덱스에 해당하는 수와 R의 첫 번째를 제외한 나머지 세 자리에 해당하는 수를 생성할 때 Math.floor로 소수점을 버려야했는데 '정수 부분을 파싱해야지...' 라는 생각에 parseInt를 사용해버렸다. 타입에 관대한 JS였기에 해당 코드가 오류가 나지 않았을 뿐, 😭 parseInt는 문자열에서 정수를 파싱하는 메서드다 !

 

2. 가독성과 교환한 시간 & 메모리 : 위의 최종 제출 코드에서 작성한 checkNum 함수는 리팩토링 하면서 생겨난 util이다. 원래는 ... 

// 입출력 생략
const solution = ([num, target]) => {
  const visited = new Array(10001).fill(null);
  visited[num] = "";
  const queue = [num];

  while (queue.length > 0) {
    let current = queue.shift();

    if (current === target) {
      console.log(visited[current]);
      return;
    }

    let D = (current * 2) % 10000;
    if (visited[D] === null) {  // 반복되는 부분
      queue.push(D);
      visited[D] = visited[current] + "D";
    }

    let S = current === 0 ? 9999 : current - 1;
    if (visited[S] === null) {  // 반복되는 부분
      queue.push(S);
      visited[S] = visited[current] + "S";
    }
    
    let L = Math.floor(current / 1000) + (current % 1000) * 10;
    if (visited[L] === null) {  // 반복되는 부분
      queue.push(L);
      visited[L] = visited[current] + "L";
    }

    let R = (current % 10) * 1000 + Math.floor(current / 10);
    if (visited[R] === null) {  // 반복되는 부분
      queue.push(R);
      visited[R] = visited[current] + "R";
    }
  }
};

 

위와 같이 작성했는데, DSLR 명령어 별 visited 방문여부 판별과 명령어를 입력하는 로직이 4번이나 반복되어 따로 함수로 만들게 되었다.

함수 분리와 L과 R 명령어 로직 개선 등 리팩토링의 흔적 🤔

 

동일한 코드를 함수 분리만 다르게 해서 제출해보니 메모리와 시간이 조금 더 소요되는 것을 확인할 수 있다. (첫 번째 줄과 네 번째 줄의 비교) 프로젝트를 진행할 때 기능에 따라 컴포넌트를 분리하던 습관을 계속 가져가고 싶어서 알고리즘 풀이에도 적용해보고, 가독성과 메모리와 시간이 어떻게 교환되었는지 확인하게 된다.

 

 

3. L과 R 명령어의 구현 방식 : 시간을 약 40% 개선할 수 있었던 부분이다. 최초의 시도는 ...

let L = ('000' + String(current)).slice(-4);
L = Number(L.substring(1) + L[0]);

 

0을 냅다 붙이고, 뒤에서부터 네 자리 수를 자른다음에, 다시 슬라이싱을 통해 L을 만들었다. 그러다가 파이썬으로 이러한 숫자/문자 포매팅을 할 땐 zfill()을 유용하게 사용했던 것이 기억이 나 padStart를 활용하는 방법으로 전환했다.

let tempNum = String(current).padStart(4, "0");

let L = parseInt(tempNum.substring(1) + tempNum[0]);
let R = parseInt(tempNum.slice(-1) + tempNum.substring(0, 3));

 

current를 문자열로 바꾼 후 padStart() 메서드로 네 자리 문자열로 tempNum에 할당한 후, 슬라이싱한 문자열을 조합하는 방식이었다. 하지만 tempNum이라는 새로운 변수를 사용하는데다가 문자로 변환하고 슬라이싱과 조합과 다시 정수로 변환하는 과정이 상당히 비효율적인 것 같아서 연산을 통해 구현했다.

let L = Math.floor(current / 1000) + (current % 1000) * 10; // 앞 세 자리 + 나머지 한 자리
let R = (current % 10) * 1000 + Math.floor(current / 10); // 앞 한 자리 + 나머지 세 자리