#백준_1019 책 페이지 - Java

#유형 : 탐색

# 많이 어려웠던 문제... 풀다가 메모리초과, 시간초과 때문에 도저히 모르겠어서 백준님 슬라이드를 통해 이해하고 풀었다.

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

 

우선 시작 숫자와 마지막 숫자의 일의 자리수를 0과 9로 맞춘다.

쉽게 설명하자면 만약 10에서 29사이의 사용된 0~9 숫자를 구하면 다음과 같다.

 

10	11	12	13	14	15	16	17	18	19
20	21	22	23	24	25	26	27	28	29

일의 자리만 보면 된다. 0~9사이가 2개씩 나왔다. (2-1+1)*1 => 2

 

다른 예로, 일의 자리 기준으로 생각해보자.  1350 ~ 8739 는 (873-135+1)*1 . 따라서 arr[0~9] 에는 873-135+1 를 더할수 있다.

그 다음에는 십의 자리를 구해보면 된다. 각 숫자를 10으로 나눠준다. 135 ~ 873 를 각각  ++, -- 를 통해 140 ~ 869로 만들어준다.

140 ~ 869 는 86 - 14 + 1 을 더할수 있다. 이 때 지금 구하고 있는 숫자는 십의 자리이므로  * 10을 해줘야 한다.

 

아래의 경우에 숫자들 뒤에 0~9가 붙어있는 것이다. 따라서 10을 곱해줘야한다.

10	11	12	13	14	15	16	17	18	19
20	21	22	23	24	25	26	27	28	29

이렇게 곱하는 숫자를 10씩 곱해주고, 시작숫자와 마지막 숫자를 10으로 나눠가면서 구하면 된다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p1019 {
    static int N;
    static int start,end;
    static int multi=1;
    static int arr[] = new int[10];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        start = 1;
        end = N;
        
        
        while(start<=end) {
            
            while(start%10!=0 && start<=end) {
                solve(start);
                start++;
            }
            
            if(start>end)
                break;
            
            while(end%10!=9 && start<=end) {
                solve(end);
                end--;
            }
            start/=10;
            end/=10;
            
            
            for(int i=0; i<10; i++) {
                arr[i] += (end-start+1)*multi;
            }
            multi*=10;
            
        }
        
        for(int i=0; i<10; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    private static void solve(int s) {
        // TODO Auto-generated method stub
        while(s>0) {
            arr[s%10]+=multi;
            s/=10;
        }
    }
}