[Algorithm] 리모컨 (백준 - 1107)

📋 문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

• 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

• 첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

입출력 예

예제 입력	예제 출력
5457 3 6 7 8	6

✏️ 풀이

경우에 따른 처리를 잘 해야하는 문제라고 생각했다.

 

100번 채널에서 시작하기 때문에 번호 버튼을 눌러 채널을 옮기는 것과 +-버튼만 누르는 것이 좋은지 확인해야 한다. 내 경우 답을 저장하는 cnt에 초기값으로 100번에서 시작해 +-만 이용해 목표 채널 N으로 옮기는 경우로 설정했고, 모든 경우를 탐색하며 더 작은값으로 갱신시켰다.

 

만약 현재 채널이 100인데 100의 채널로 옮기는 경우가 존재하기 때문에 만약 N이 100이라면 0을 출력하고 그렇지 않은 경우에 가장 최솟값을 계산한다. 이때 고장난 버튼을 Set 자료구조에 저장해서 값이 있는지 없는지를 판별했다. 모든 경우를 계산하면서 0부터 1,000,000까지를 범위로 잡았는데 그 이유는 목표채널이 최대 500,000이기 때문에 두 배로 산정했다.

 

사실 처음 이 범위 생각할 때 N * 2로 잡았었는데 계속 "틀렸습니다"라는 문구를 마주쳐야 했다. 여러 예외를 생각하다가 0인 경우를 생각하게 되었고 1,000,000으로 수정하게 되었다.

 

반복문을 돌며 i가 만들어지는 숫자가 된다. 이를 타입변환을 통해 문자열로 바꾸고 각 자리에 고장난 버튼이 포함되어 있는지를 확인했다. 만약 고장난 버튼이 있다면 누를 수 없는 번호이기 때문에 외부 반복문(for)를 continue 시켜주고 그렇지 않은 경우 N과 비교하고 자리수를 더해 최소값을 가지는 cnt에 대소를 비교하며 갱신했다. 결국 반복문이 종료되면 cnt에 있는 값이 가장 최소가 되어 출력하며 문제를 해결했다.

⌨️ 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './testcase/1107.txt';

let input = fs.readFileSync(filePath).toString().trim().split('\n');

const target = input[0];
if (target === '100') console.log(0);
else {
  const disableBtn = +input[1] ? new Set(input[2].split(' ')) : new Set();
  let cnt = Math.abs(+target - 100);

  outer: for (let i = 0; i <= 1000000; i++) {
    const check = String(i);
    for (let j = 0; j < check.length; j++) {
      if (disableBtn.has(check[j])) continue outer;
    }

    const compare = Math.abs(+target - i) + check.length;
    cnt = Math.min(compare, cnt);
  }

  console.log(cnt);
}