[백준] 1748번 수 이어 쓰기 1

1) 생각

숫자 N을 주어준 후 1부터 N까지 숫자를 쭉 이었을 경우 그 숫자의 자리수를 구하라.

1) 첫번째 생각

시간이 1초로 주어졌고 N의 범위가 1부터 1억 까지이므로 될까? 싶어서 반복문을 통해 1부터 N까지 돌리면서 그 숫자의 길이를 구해 계속 더해주었다. 약간 느리고 메모리를 많이 잡아먹었지만 '맞았습니다'가 표시되었다.

아마 위의 방법으로는 숫자가 좀 더 크게 주어지면 '틀렸습니다'가 표시될 것이므로 다른 방법을 생각해보았다.

2) 방안

더 좋은 방법이 무엇일까? 처음 N이 100으로 주어지면 1~99 까지는 무조건 포함이 된다. 여기에 다음과 같은 규칙이 들어간다.

1~9는 9개

10~99는 90개

100~999는 900개

... 뒤에는 계산해 보지 않았지만 계속 저렇게 늘어날 것이 분명하다. 자연에는 규칙이 있으니까!

만약 100이 N으로 주어진다면 N의 길이 3을 받고 반복문을 통해 길이 1,2의 해당하는 개수를 모두 더해준 후(1*9 , 2*90) 자신의 길이는 자신의 길이 시작 숫자부터 자신까지의 개수만큼 더해주었다. 그 결과 첫번째 생각과의 차이는 상당했다!

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int len = String.valueOf(n).length();
        int gu = 9;
        int result = 0;
        // 자리수 이하의 자리수는 모두 들어간다.
        // 1자리 9 2자리 90 3자리 900 ....
        for(int i=1;i<len;i++) {
            result += i*gu;
            gu*=10;
        }
        // 마지막 자신의 자리수는 자신 - 그 자리수의 시작 * 자리수
        result += (n-(int)Math.pow(10, len-1)+1) * len;
        System.out.println(result);
    }
}