백준 1019번 책 페이지 :: 마이구미

이번 글은 백준 알고리즘 1019번 "책 페이지" 를 다뤄본다.

모 회사에서도 코딩 테스트로 출제되었다고 한다.

문제 풀이는 규칙을 찾은 후 구현해야하는 수학적인 사고가 필요하다.

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

문제는 보다시피 정말 간단하다.

본인은 백준 사이트의 CEO 백준님의 자료를 통해 문제를 해결했다. 참고 자료

자료를 보더라도, 이해하기가 쉽지 않았다.

참고 자료를 보면 1 ~ N이 아닌 A ~ B를 예로 들었다.

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

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

특정 숫자의 각 자릿수를 뽑을 때는, % 10, / 10 를 통해 할 수 있다.

1234
1234 % 10 = 4
1234 / 10 = 123 => 123 % 10 = 3
123 / 10 = 12 => 12 % 10 = 2
12 / 10 = 1 => 1 % 10 = 1

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;
    }
}

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;
    }
}