백준 1019번: 책 페이지

문제 출처: https://www.acmicpc.net/problem/1019

참고출처 

http://mygumi.tistory.com/180?category=689691, https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

N이 36일 때,

 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 34 35 36

10~29는 일의 자리가 0~9까지 한 번씩 나오며, 십의자리에서 숫자 1와 2는 열 번씩 나온다. 

1) 1~9와 30~36의 숫자는 각 숫자가 몇 번씩 나오는지 일일이 계산해 더한다. 

이때, 1에서부터는 끝자리가 0이 나올 때까지 더해주고, 36에서부터 끝자리가 9가 나올 때까지 빼면서 계산한다.

 

2) 10~29까지의 숫자는 일의 자리, 십의 자리씩 끊어서 계산한다.

십의 자리가 1와 2일 때, 일의 자리에서 0~9는 총 (2-1+1)*1번씩 나오고, 십의 자리에서 1와 2는 1*10번씩 나온다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    
    private static int[] numArr = new int[10];
    private static int position = 1;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine()); // 36
        int start = 1;
        int end = N;
        
        while(start <= end) {
            
            while(start%10!=0 && start<=end){
                cal(start);
                start++; // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
            }
            
            if(start > end)
                break; // 계산 종료
            
            while(end%10!=9 && start<=end){
                cal(end);
                end--; // 36, 35, 34, 33, 32, 31, 30, 29
            }
            
            start /= 10;  // 10 -> 1 
            end /= 10;  // 29 -> 2
            
            for(int i=0 ; i<10 ; i++)
                numArr[i] += (end-start+1) * position;  // 일의 자리에 0~9가 총 2번씩 등장
            
            position *= 10;  // 자리수 계산
        }
        
        StringBuilder builder = new StringBuilder();
        for(int i=0 ; i<10 ; i++)
            builder.append(numArr[i] + " ");
        
        System.out.println(builder.toString());
    }
    
    public static void cal(int num){ // 각 숫자가 몇 번씩 나오는지 더함
        while(num > 0){
            numArr[num%10] += position;
            num /= 10;
        }
    }
}