[백준 1107 - Node.js] 리모컨

🔗 문제 링크

https://www.acmicpc.net/problem/1107

1107번: 리모컨

✏️ 풀이

const [N, M, nums] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const brokens = nums
  ? nums
    .split(' ')
    .reduce((acc, v) => {
      acc[v] = true;
      return acc;
    }, {})
  : {};

let count = Math.abs(100 - N);
for (let i = 0; i < 1_000_000; i++) {
    const numString = i.toString();
    let isValid = true;
    for (let j = 0; j < numString.length; j++) {
        if (brokens[numString[j]]) {
            isValid = false;
            break;
        }
    }
    if (isValid) {
        count = Math.min(count, Math.abs(i - N) + numString.length);
    }
}

console.log(count);

고장나지 않은 숫자 버튼으로 이동할 수 있는 모든 채널들 중에서 가장 적은 횟수로 버튼을 누르는 경우를 찾아야 한다. 이동하고자하는 채널 N의 최댓값은 500,000이지만 처음에 숫자 버튼을 눌러서 500,000보다 더 높은 채널로 이동 후 -버튼으로 목표 채널을 찾아갈 수도 있기 때문에, 0부터 999,999까지의 모든 수에 대해서 탐색하였다.

 

 

const [N, M, nums] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const brokens = nums
  ? nums
    .split(' ')
    .reduce((acc, v) => {
      acc[v] = true;
      return acc;
    }, {})
  : {};

let count = Math.abs(100 - N);
const dfs = (nextChannel = '') => {
  if (nextChannel) {
    const curCount = Math.abs(nextChannel - N) + nextChannel.length;
    count = Math.min(count, curCount);
  }

  if (nextChannel.length <= N.length) {
    for (let i = 0; i < 10; i++) {
      if (brokens[i] || nextChannel === '0') {
        continue;
      }
      dfs(nextChannel + i);
    }
  }
};

if (M) {
  dfs();
}
console.log(count);

처음에 DFS로 위와 같이 풀었으나 시간이 4배 이상 더 걸렸었다. 꼭 필요한 경우가 아니라면 재귀호출은 삼가야 할 것 같다.