🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let n = +fs.readFileSync(path).toString().trim();
const numbers = Array(10).fill(0);
let digit = 1;
let add = 0;
while (n > 0) {
const rest = n % 10;
n = Math.floor(n / 10);
for (let i = 0; i <= 9; i++) {
if (i < rest) numbers[i] += (n + 1) * digit;
else if (i === rest) numbers[i] += n * digit + add + 1;
else numbers[i] += n * digit;
}
add += rest * digit;
numbers[0] -= digit;
digit *= 10;
}
console.log(...numbers);🟢 풀이
⏰ 소요한 시간 : -
맨 처음엔 DP인가? 생각했었는데 규칙을 찾다보니 수학 문제임을 알았다.
구현방법을 한번에 떠올리지는 못해서 출처를 참고해 이해한 방식대로 풀어봤다.
책 페이지에서 각 숫자가 몇번 나오는지 체크해주는 문제로 n에서 1의 자리에 각 수가 몇번 나오는지 체크해주면 된다.
그럼 10의 자리나 100의 자리는 어떻게 계산할까?
n을 10으로 나누면 10의 자리는 1의 자리가 되기 때문에 우리는 1의 자리수만 고려하면 된다.
예를 들어보자. n = 334일 경우 1의 자리만 봤을 때, 4를 기준(334%10)으로 0부터 4까지는 각 수가 35번, 5부터 9까지는 각 수가 34번 나온다.
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
...
90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109
...
320 321 322 323 324 325 326 327 328 329
330 331 332 333 334이 때 n은 자연수라는 조건이 있으므로 맨 앞의 0은 제거를 해줘야 한다.
위를 기반으로 코드를 설계하면 다음과 같은 식이 나온다.(digit == 1)
const rest = n % 10;
n = Math.floor(n / 10);
for (let i = 0; i <= 9; i++) {
if (i < rest) numbers[i] += (n + 1) * digit;
else numbers[i] += n * digit;
}
numbers[0] -= digit;이제 10의 자리를 고려하기 위해 n을 10으로 나누어 33으로 만들어서 다시 계산한다.
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 이 경우도 마찬가지로, 3을 기준(33%10)으로 0부터 3까지는 각 수가 4번 5부터 9까지는 각 수가 3번 나온다. 마찬가지로 0 제외.
그런데 위 상황은 10의 자리를 고려한 것이다. 따라서 하나의 수에 0부터 9까지 총 10개의 수가 붙을 수 있다.
0(0~9) 1(0~9) 2(0~9) 3(0~9) 4(0~9) 5(0~9) 6(0~9) 7(0~9) 8(0~9) 9(0~9)
...
30(0~9) 31(0~9) 32(0~9) 33(0~9) 그래서 n을 10으로 나눠줄 때 마다 digit에는 10을 곱해 계산한다.
const rest = n % 10;
n = Math.floor(n / 10);
for (let i = 0; i <= 9; i++) {
if (i < rest) numbers[i] += (n + 1) * digit;
else numbers[i] += n * digit;
}
numbers[0] -= digit;
digit *= 10;마지막으로 하나의 상황을 더 고려해야 한다.
0(0~9) 1(0~9) 2(0~9) 3(0~9) 4(0~9) 5(0~9) 6(0~9) 7(0~9) 8(0~9) 9(0~9)
...
30(0~9) 31(0~9) 32(0~9) 33(0~4)33같은 경우 다른 수처럼 0부터 9까지 수를 모두 포함하는 것이 아니고, 0부터 4까지만 포함하게 된다. 여기서 4는 이전 반복에서 334를 10으로 나눈 나머지가 된다.
const rest = n % 10;
n = Math.floor(n / 10);
for (let i = 0; i <= 9; i++) {
if (i < rest) numbers[i] += (n + 1) * digit;
else if (i === rest) numbers[i] = n * digit + add + 1;
else numbers[i] += n * digit;
}
add += rest * digit;
numbers[0] -= digit;
digit *= 10;정리하면 현재 i가 n을 10으로 나눈 나머지 rest인 경우에만 n*digit + add(4) +1(0포함)을 해줘야 한다.
이 때 add는 이전단계의 n을 10으로 나눈 나머지가 된다. 단 digit가 증가할때마다 나머지에 digit를 곱해야 한다는 점
🔵 Ref
