[백준 BOJ] 1019번 책 페이지

백준 BOJ 1019번 책 페이지

 

책 페이지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	3082	630	484	36.890%

문제

지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다.

예제 입력 1

 

11

예제 출력 1

 

1 4 1 1 1 1 1 1 1 1

힌트

출처

• 문제를 번역한 사람: baekjoon

 

---

풀이

private void solve() {
    // http://mygumi.tistory.com/180
    int page = sc.nextInt();
    int[] ans = new int[10];
    int point = 1;
    int start = 1;
 
    while (start <= page) {
        // 끝자리 9로 만들기
        while (page % 10 != 9 && start <= page) {
            cal(page, ans, point);
            page--;
        }
 
        if (page < start) {
            break;
        }
 
        // 끝자리 0으로 만들기
        while (start % 10 != 0 && start <= page) {
            cal(start, ans, point);
            start++;
        }
 
        start /= 10;
        page /= 10;
 
        for (int i = 0; i < 10; i++) {
            ans[i] += (page - start + 1) * point;
        }
 
        point *= 10;
    }
 
    for (int i = 0; i < 10; i++) {
        System.out.print(ans[i] + " ");
    }
 
}
 
public static void cal(int x, int[] ans, int point) {
    while (x > 0) {
        ans[x % 10] += point;
        x /= 10;
    }
}

 

핵심은 A는 일의 자리가 0이 되어야하고, B는 일의 자리가 9가 되어야하고, 각 자릿수를 나누어서 생각한다.

(일의 자리에 대한 횟수, 십의 자리에 대한 횟수, 백의 자리에 대한 횟수.....)

 

0, 9를 만들어야하는 이유는 아래와 같은 규칙 때문이다.

A = 10, B = 39인 경우를 보자.

• 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, 37, 38, 39

보다시피 0 ~ 9의 횟수의 규칙을 볼 수 있다.

각 수의 횟수는 3 - 1 + 1 로 구할 수 있다. (39 / 10 = 3, 10 /10 = 1 || B / 10 - A / 10 + 1)

십의 자리, 백의 자리를 구할 때도 동일하다.

A = 1345 B = 8742 ==> A = 1350 B = 8739 일의 자리

-> 0~9의 각 횟수 (873 - 135 + 1) * 1 

A = 135 B = 873 ==> A = 139 B = 869 십의 자리

-> 0~9의 각 횟수 (86 - 13 + 1) * 10

A = 13 B = 36 ==> A = 19 B = 29 백의 자리

-> 0~9의 각 횟수 (2 - 1 + 1) * 100 

A = 1 B = 2 ==> 천의 자리

구현 방식은 위처럼 순서대로 하면 된다.

 

1. 페이지의 번호의 일의 자리를 9로 만든다.

2. 시작 번호의 일의 자리를 0으로 만든다.

3. 만들어진 두 수를 규칙을 이용해 0~9의 횟수를 추가한다. (B / 10 - A / 10 + 1)

 

 

0과 9를 만드는 과정에서의 횟수는 단순히 자릿수를 더하면 된다.

예를 들어, 십의 자리를 구하기 위해 135 -> 136을 바꾸는 과정을 보자.

135은 사실상 1350이기 때문에, 1350 -> 1360으로 바꾸는 과정이 된다.

결과적으로 1이 10번, 3이 10번, 5가 10번 나오게 된다.

이 부분은 코드 중 아래 코드가 된다.

public static void cal(int x, int[] ans, int point) {
    while (x > 0) {
        ans[x % 10] += point;
        x /= 10;
    }
}

출처: http://mygumi.tistory.com/180 [마이구미의 HelloWorld]