백준 | 1748. 수 이어 쓰기 1
이 포스트는 제가 개인적으로 공부한 내용을 정리한 글입니다. 잘못된 내용이나 부족한 부분 등 자유로운 피드백은 저에게 큰 도움이 됩니다!
문제
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223…
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.
첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.
예 1
Input: 120
Output: 252
// 12345678...120 총 길이가 252내용
이 문제는 입력받은 숫자 N을 1부터 N까지 수를 쭉 이었을 때의 총 길이를 구하는 문제이다.
일반적인 방법으로는 1부터 입력받은 숫자만큼 반복문을 돌리면서 숫자를 문자형으로 형 변환하여 더한 다음 총 길이를 구하는 방법이 있다. 하지만 이런 방식으로 풀게 되면 최대 입력값이 1억이기 때문에 메모리 초과로 문제를 풀 수 없다.
/**
* 예제 120은 통과할 수 있지만 입력 최대값이 1억이기 때문에 메모리 초과로 문제를 풀 수 없다.
*/
const num = 120;
let strNum = "";
start = new Date().getTime();
for (let i = 1; i <= 1000; i++) {
strNum += String(i);
}
var elapsed = new Date().getTime() - start;
console.log(strNum.length, elapsed); // log: 252따라서 더 효율적인 방법을 찾아야 하는데 이 문제를 보게 되면 보이는 규칙이 있다.
- 1-9까지 9개 * 1(자릿수) = 9
- 10 - 99까지 90개 * 2(자릿수) = 180
- 100 - 999까지 900개 * 3(자릿수) = 2700
이렇게 개수 * 자릿수를 통해 각 자릿수의 총 길이를 알 수 있다.
즉, 예제 120의 경우, 9 + 180 + (120 - 100 + 1(100도 포함)) * 3(자릿수)가 된다.
이대로 구현만 하면 된다.
// 입력을 받는다.
const fs = require('fs')
const strLine = fs.readFileSync('/dev/stdin').toString().split("\n");
// 입력값은 문자형이기 때문에 숫자형으로 형 변환한다.
const n = parseInt(strLine[0], 10);
function solution(n) {
// 입력값의 길이
const l = String(n).length;
let answer = 0;
for(let i = 1; i < l; i++) {
// 입력값 아래의 자릿수 총 길이를 구한다.
answer += i * (10 ** i - (10 ** (i - 1)))
}
// 입력값 자릿수의 개수를 구하고 자릿수를 곱해 길이를 구한다.
answer += (n - 10 ** (l - 1) + 1) * l;
return answer
}
console.log(solution(n));초보인 나한테 어려운 문제였다. 규칙은 보이는데 구현하는데 애를 많이 먹었다.
아오 풀어보면 별거 아닌 거 같은데.. 정말 수학 잘하고 싶다..