[백준][Gold1] 책 페이지 - JAVA

[문제]

www.acmicpc.net/problem/1019

1019번: 책 페이지

[풀이]

✅구하려는 것: 1 ~ N까지의 숫자에 0~9가 각각 몇번 등장하는가

 

✅규칙

* A=1, B=N으로 둔다. (ex. A=1, B=678)

1. ☝🏼정해진 약속: A의 일의자리는 항상 0, B의 일의자리는 항상 9여야 한다.
        만약 아니라면 B--, A++ 하여 숫자를 변형해준다. 

 

 A ~ B까지 일의자리에 0~9가 몇번들어가는가

2.예시의 A=1, B=678를 위 규칙대로 변형하면 A = 10, B=669가 된다. 

이때, B = 678 -> 669로 변형되면서 숫자 669, 668, 667, 666, 665, 664, 663, 662, 661, 660 은 지나갔다.

지나간 숫자들 페이지에 몇번 등장하는지 별도로 먼저 계산해준다. 

 

3. B를 먼저 계산 후에 B가 A보다 작아진다면 계산을 멈춘다. 
    아니면 A도 2와같은 방법으로 계산한다. 

 

4. 2,3에서 B--, A++ 하여 A=10, B=669가 되었다. 

    그럼 A~B까지 일의자리에는 0~9가 동일하게 각각 (1 - 1 + 1)번 등장한다. 

    ▶일의자리에 등장하는 횟수 =  (B/10) - (A/10) + 1 

 

 A ~ B까지 십의자리에 0~9가 몇번들어가는가

5. 이후 A = A/10, B = B/10 으로 변형해준다. 
     A = 1, B = 66이 된다. 

 

6. A의 일의자리가 0이 아니고, B의 일의자리도 9가 아니다. 

   다시 정해진 약속을 지키기 위해 B--, A++ 를 해주고 지나가는 숫자들은 별도로 페이지에 등장하는 횟수를 계산해준다. 

 

7. A = 10 , B= 59가 된다. 
   그럼 A ~ B까지 십의자리에는 0~9가 동일하게 각각 (5 - 1 + 1) 번 등장할까?
   아니다. 10의 자리숫자는 곱하기 10을 해줘야 한다. 

 ▶일의자리에 등장하는 횟수 = ((B/10) - (A/10) + 1) * 10;

 

이와 같이 100의 자리 숫자는 곱하기 100, 천의 자리 숫자는 곱하기 1000을 한다. 

 

참고 
www.slideshare.net/Baekjoon/baekjoon-online-judge-1019
settembre.tistory.com/255

[code]

package com.algorithm.baekjoon.gold;

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

public class Test02 {
    public static int[] pages = new int[10]; // 0 ~ 9의 등장 횟수를 담는 배열
    public static int count = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());
        solution(N);
    }

    public static void solution(long N) {
        long A = 1;
        long B = N;

        while (A <= B) {
            // 1의 자리
            int oneA = (int) (A % 10);
            int oneB = (int) (B % 10);

            if (oneB < 9) {
                for (int i = 1; i <= oneB + 1; i++) {
                    // B가 0보다 작거나 같다면 계산을 몀춘다.
                    if (B <= 0) {
                        break;
                    }
                    cal(B);
                    B--;
                }
            }
            
            if (B < A) {
                break;
            }

            if (oneA > 0) {
                for (int i = 1; i <= 10 - oneA; i++) {
                    cal(A);
                    A++;
                }
            }

            for (int i = 0; i < pages.length; i++) {
                pages[i] += (B / 10 - A / 10 + 1) * count;
            }

            count *= 10;
            A = A / 10;
            B = B / 10;
        }

        for (int i = 0; i < pages.length; i++) {
            System.out.print(pages[i] + " ");
        }
    }

    public static void cal(long N) {
        while (N > 0) {
            int num = (int) (N % 10);
            pages[num] += count;
            N = N / 10;
        }
    }
}