백준 1107 < 리모컨 > JavaScript

📍문제 링크

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

1107번: 리모컨

 

📍알고리즘 분류

- 브루트포스

 

📍문제 풀이

아직 완전탐색(브루트포스) 이외의 풀이법은 못찾았다.

N이 주어질 때, N이 가능한 범위를 최대한 줄여서 완전탐색을 실행하면 된다.

코너 케이스가 매우 많아서 정답률이 매우 낮다.

 

📍코드 (JavaScript)

const [in1, in2, in3] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const N = +in1; // 숫자 N
const len = in1.length; // N의 길이
const closedButtonNum = +in2; // 고장난 버튼 갯수
let closedButtons;
// 초기값은 100에서부터 하나씩 만들어가는 naive solution (worst case)
let answer = Math.abs(N - 100);

const solution = () => {
  // 고장난 버튼이 없으면 마지막 입력값이 주어지지 않음
  if (closedButtonNum === 0) {
    return len < answer ? len : answer;
  }
  // 전부 다 고장났으면 1씩 이동
  if (closedButtonNum === 10) return answer;
  // 고장난 버튼이 존재하면 마지막 입력에서 구해줌
  closedButtons = in3.split(" ").map(Number);
  // 가능한 버튼들을 구해줌 (오름차순)
  const openButtons = [];
  for (let i = 0; i < 10; i++) {
    if (!closedButtons.includes(i)) openButtons.push(i);
  }
  // 가능한 버튼이 0만 있다면
  // 1. 0 누르고 +1 진행
  // 2. 100 에서 +1 or -1 진행
  if (openButtons.length === 1 && openButtons[0] === 0)
    return Math.min(answer, 1 + N);

  // 완전 탐색을 위한 범위 설정
  // 최솟값
  // 1. 가능한 버튼 중 가장 작은 수를 N개 만큼 채움
  // 2. 가능한 버튼 중 가장 작은 수가 0이면
  //  2.1. N이 한 자리 수 일 때 최솟값 0으로 설정 // FIXME 개선 가능
  //  2.2. N이 2자리 수 이상일 때는 N -1 자릿수를 가능한 버튼중 최댓값으로 채움
  // ->  1000 일 때 999 에서 접근하도록
  let minNum = parseInt(openButtons[0].toString().repeat(len));
  if (closedButtons.includes(0)) {
    if (len !== 1) {
      minNum = parseInt(
        openButtons[10 - closedButtonNum - 1].toString().repeat(len - 1),
      );
    } else {
      minNum = 0;
    }
  }
  // 최댓값
  // 1. 가능한 버튼 중 가장 큰 수를 N개 만큼 채움
  // 2. 가능한 버튼 중 가장 큰 수가 9이면
  // 2.1. 0 다음 작은 수로 N + 1 자릿수로 채움
  // -> 9999 일 때 10000에서 접근하도록
  let maxNum = parseInt(
    openButtons[10 - closedButtonNum - 1].toString().repeat(len),
  );
  if (closedButtons.includes(9)) {
    if (!openButtons.includes(0))
      maxNum = parseInt(openButtons[0].toString().repeat(len + 1));
    else maxNum = parseInt(openButtons[1].toString().repeat(len + 1));
  }
  // 누르는 횟수를 계산하는 함수
  const calcCount = (num) => {
    const text = num.toString();
    for (let char of text) {
      if (closedButtons.includes(+char)) return;
    }
    return Math.abs(N - num) + num.toString().length;
  };

  for (let i = minNum; i <= maxNum; i++) {
    const result = calcCount(i);
    if (result) answer = Math.min(answer, result);
  }
  return answer;
};

console.log(solution());

 

📍리뷰

- 최솟값과 최댓값을 정하는 로직을 간편하게 개선할 수 있을것 같다! 리팩토링 필요