[백준] 1107 리모컨 : 자바스크립트(node.js)

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

문제

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

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1

5457
3
6 7 8

 

예제 출력 1

6

 

풀이방법

 

수빈이는 왜 버튼을 세게 줄러서 고장나게 만들었을까..........

 

여기서 고려해야 할 것은

1. 고장난 버튼은 누를 수 없다

2. 시작은 100번이다

 

고장난 버튼 누를 수 없는건 말 그대로고

시작이 100번이기때문에 만약 102번으로 가야한다? 그럼 1 0 2 세번 누를 필요 없이 +를 두번 하면 된다

 

그리고 이건 ....완탐이다

처음엔 while문으로 어떻게 해보려고 했는데 로직이 안나올것같아서

그냥 주어진 조건의 숫자들을 다 살피고 최솟값만을 저장하게 하자

 

첫 풀이

 

if (list !== undefined) {
    for (let n = 0; n <= 999999; n++) {
      const stn = n.toString();
      for (let i = 0; i < list.length; i++) {
        for (let j = 0; j < stn.length; j++) {
          if (stn.charAt(j) === list[i].toString()) {
            canMove = false;
            break;
          }
        }
        if (!canMove) break;
      }
      if (canMove) minRes = Math.min(minRes, stn.length + Math.abs(N - n));
      canMove = true;
    }
    minRes = Math.min(minRes, Math.abs(N - 100));
  } else {
    minRes = N.toString().length;
  }

 

이게 고장난 버튼이 0인 경우는 이후의 버튼 배열이 아예 들어오지 않기 때문에 undefined 조건문을 분리해줬다

그리고 딱 봐도 별로인 3중포문,,,,,,,

1. 가능한 모든 숫자들을 보고

2. 주어진 고장난 버튼 배열을 확인하고

3. 현재의 숫자와 같은지 비교해서

고장난 버튼 숫자와 하나라도 겹치면 false로 빼버린다

 

그리고 고장난 버튼을 누르지 않는다면(canMove) 그 채널 숫자를 누르는 길이와 (564번이면 5 6 4 일단 3번을 눌러야 한다), 플러스 아니면 마이너스로 원하는 채널까지 버튼 눌러줘야하니까 Math.abs(N - n)을 더해준 값을 구해준다

 

그리고 우리는 시작이 100인 것도 고려해야 하기 때문에 위에서 for문을 돌면서 구한 minRes와 N - 100의 절댓값을 비교해서 더 작은걸 저장한다.

 

만약 고장난 버튼이 없는 경우는 그냥 그 숫자를 모두 누르도록 했는데

저건 96퍼에서 틀렸습니다가 뜬다

하

하하

ㅎㅏ

왜일까요

 

원인은 간단했다... 고장난 버튼이 없는 경우에 100과 가까운 경우를 고려하지 않았다

바본가? 위에서는 열심히 해놓고

아무튼 저걸 고친 다음 코드로 제출하면 맞았습니다를 받을 수 있긴 하다

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

const N = input[0][0];

const list = input[2];

const solution = () => {
  let canMove = true;
  let minRes = Number.MAX_SAFE_INTEGER;

  if (list !== undefined) {
    for (let n = 0; n <= 1000000; n++) {
      const stn = n.toString();
      for (let i = 0; i < list.length; i++) {
        for (let j = 0; j < stn.length; j++) {
          if (stn.charAt(j) === list[i].toString()) {
            canMove = false;
            break;
          }
        }
        if (!canMove) break;
      }
      if (canMove) minRes = Math.min(minRes, stn.length + Math.abs(N - n));
      canMove = true;
    }
    minRes = Math.min(minRes, Math.abs(N - 100));
  } else {
    minRes = Math.min(N.toString().length, Math.abs(N - 100));
  }
  console.log(minRes);
};

solution();

 

그치만? 아무리봐도 저 3중포문이 맘에 안든다... 고쳐보자

for문을 하나정도는 줄일 수 있지 않을까,,,해서

 

애초에 고장난 버튼 배열을 받아서 boolean으로 배열에 저장하고 해당 인덱스로 가져오면 되겠다

let check = new Array(10).fill(true);
for (let i = 0; i < list.length; i++) {
    check[list[i]] = false;
}

이렇게!

이 코드 역시 undefined를 고려하는 if문의 내부에 있어야 한다

 

그럼 위에서 만든 3중포문 중 list를 고려하는건 필요없어진다

stn.charAt(j) - "0" 얘를 인덱스로 갖는 check 배열이 false이면 얘는 틀린 버튼인거니깐

for문을 돌리는게 아니라 인덱스로 바로 값을 찾는 방식인거다

 

그러면 for문 중간의 

if (!canMove) break;

는 필요 없어진다!

그냥 canMove = true일때만 minRes를 계산해주면 된다

 

그렇게 최종 코드는 

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

const N = input[0][0];
const list = input[2];

const solution = () => {
  let minRes = Number.MAX_SAFE_INTEGER;

  if (list !== undefined) {
    let check = new Array(10).fill(true);
    for (let i = 0; i < list.length; i++) {
      check[list[i]] = false;
    }
    for (let n = 0; n <= 1000000; n++) {
      let canMove = true;
      const stn = n.toString();
      for (let j = 0; j < stn.length; j++) {
        if (!check[stn.charAt(j) - "0"]) {
          canMove = false;
          break;
        }
      }
      if (canMove) minRes = Math.min(minRes, stn.length + Math.abs(N - n));
    }
    minRes = Math.min(minRes, Math.abs(N - 100));
  } else {
    minRes = Math.min(N.toString().length, Math.abs(N - 100));
  }
  console.log(minRes);
};

solution();

짜잔

 

두 최종코드의 차이는 다음과 같다

어차피 완탐이라 메모리 사용량은 비슷한데 속도는 꽤 차이가 난당!