엉금엉금

N의 숫자가 10억이기에, 각각의 페이지를 일일이 확인해서는 풀 수 없는 문제입니다.

따라서 각각의 자릿수에 대해서 해당 숫자가 몇번 나올지 측정을 합니다.

1. 0~9까지 공통적으로 반복되는 횟수를 측정.

20을 예로 들면  일의 자리에서 0~9 까지는 총 2번 반복됩니다. 이를 부모의 값을 통해서 측정을 합니다.

220 을 예로 들면 0~9까지는 총 22번 반복되게 됩니다.

이때 유의 해야 할 점은 0입니다.  페이지가 01이 아닌 1 페이지기 때문에, 이 0에 의해서 오류가 자주 생깁니다.

201 의 경우에는 

나머지는 두 번째 자리에 대해서는 20번씩 반복되지만 0의 경우는 12번만 반복됩니다. 즉 0의 경우에는 하위 자릿수에 대한 영향도 받음을 알 수 있습니다.

100~ 109 , 200~201

2. 해당 숫자가 몇번까지 존재하는지

124를 예를 들겠습니다.

1의 경우에는 110~119 까지 10번 반복되는데 2의 경우에는 20~24까지 5번만 반복되는 하위 자릿수의 값에 대한 영향을 받습니다.

이 두가지를 고려해서 알고리즘을 짰습니다.

numberList :  입력값을 자릿수마다 분해해서 배열에 담음

number :  입력값을 number 타입으로 변환한 값

sames : 공통적으로 반복되는 값을 추후 각각의 숫자에 대해서 더하는 용도

answer : 그리고 각각의 숫자가 몇번 사용되었는지 담을 배열 

digit : 자릿수

depth : 해당 숫자의 부모의 자릿수 ( parentDigit)을 했으면 변수명이 더 깔끔했을 까요,,?

target : 현재 자릿수에 대한 값.

const fs = require('fs');
const input = fs.readFileSync('dev/stdin').toString();
const numberList = input.split('').map(Number);
const number = +input;

let sames = 0;

const answer = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

const digit = numberList.length;

for (let i = digit - 1; i >= 0; i--) {
  const depth = 10 ** (digit - i);
  sames += (parseInt(number / depth) * depth) / 10;
  const target = numberList[i];
  if (target === 0 && digit - i !== 1) {
    answer[0] -= depth / 10 - 1 - (number % (depth / 10));
  }
  for (let j = target; j >= 1; j--) {
    if (j === target) {
      answer[j] += (number % (depth / 10)) + 1;
    } else {
      answer[j] += depth / 10;
    }
  }
}

let counts = answer.map((e) => e + sames).join(' ');
console.log(counts);

반북문을 통해서 1의 자리부터 최고 자릿수까지 코드를 진행합니다.

우선 반복되는 값은 부모의 자릿수에 대해서 영향을 받는데 이는 부모 자릿수 까지만 값을 고려하고 나머지는 제거한 값입니다. 이후 해당 값을 10으로 나누어 주면 됩니다.(갯수 / 분모(0~9 총 10개)

ex) 105 의 경우에  10(100/10 ) 개의 0~9가 가 공통적으로 존재함 

이때 유의해야 할 점이 0이라고 하였습니다.

이를 반복문을 통해서 만약  target값이 0이고 첫번째 자릿수가 아니라면  9999~~에 현재 자릿수 이하의 값을 뺀 값을  제거해줍니다. 

105의 경우에   2번쨰 자리에 대한 sames가 10개라고 했는데 0의 경우에는 실질적으로 6개 입니다.

따라서 4개를 제거해야 하는데 이를  9(10-1) - 5 를 하면 됩니다.

  sames += (parseInt(number / depth) * depth) / 10;
  const target = numberList[i];
  if (target === 0 && digit - i !== 1) {
    answer[0] -= depth / 10 - 1 - (number % (depth / 10));
  }

마지막으로 현재 자릿수 이하의 값을 반영해줍니다.

1042의 두번 째 자리를 예로 들면

1~3까지는 0~9가 반복됩니다. 따라서  자릿수만 큼 더하면 됩니다. 하지만 4의 경우에는 0 1 2 총 3번 반복되므로, 

 for (let j = target; j >= 1; j--) {
    if (j === target) {
      answer[j] += (number % (depth / 10)) + 1;
    } else {
      answer[j] += depth / 10;
    }
  }

마지막으로  중복되는 sames값을 더한후에 출력하면 됩니다. 이때 join을 써서 하나의 문자열로 출력했습니다.

코드가 투박한 것 같아서, 추후 백준님의 풀이를 봤는데, 좀 더 문제가 심화되어도 확장성이 좋고, 함수가 분리되어 있어서 이해하기도 좋은 방식으로 코드 짠 것 같습니다... 한번 참고해 보셔도 좋을 것 같아요..

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019?qid=9aa7818e-779e-499a-9c13-d2a5ac2ef8af&v=&b=&from_search=1