[백준(JAVA)] 1748번: 수 이어 쓰기 1

문제

✔ 난이도 - Silver 4

설명

처음에는 1~N 까지 for문을 돌면서 각각의 숫자를 getDigits() 함수에서 갯수를 세서 더해주었다. 물론 통과하긴했지만 좀 단순무식한 방법.

처음 푼 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        long digitSum = 0;
        for (int i = 1; i <= N; i++){
            digitSum += getDigits(i);
        }

        sb.append(digitSum);
        System.out.println(sb);
    }

    public static int getDigits(int num){
        int count = 0;
        while (num != 0){
            count++;
            num /= 10;
        }
        return count;
    }
}

설명

그래서 두 번째엔 규칙을 찾아보았다.
구간별로 갯수에 규칙이 존재함을 알아내고 while문을 짰다.
그 이후 나머지는 while문을 벗어난 뒤 따로 처리

ex) N이 102라면 :
1 ~ 9 : 9개
10 ~ 99 : 90개
100 ~ 102 (3개) -> 102 - 100 + 1

더 좋은 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // x자리수 // 1 2 3 ... 이렇게  ++ 하면서 증가해야함
        int length = 1;

        // 1 10 100 1000 이렇게 10씩 곱하면서 커짐
        int start = 1;

        long result = 0;

        while (start * 10 <= N){ 
            result += length * (start * 9); //자리수갯수 * 해당자리수에 존재하는 숫자갯수
            length++;
            start *= 10;
        }

        result += length * (N - start + 1);

        System.out.println(result);
    }
}

루프를 한 번만 썼기때문에 처음 푼 방법보다 시간이 1/10로 줄은 것을 볼 수 있다.