🔗 전체 1019번 문제

지민이는 전체 페이지의 수가 $N$인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 $N$페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.

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

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.

• 입력

TC
1
11

• 출력

TC
1
1 4 1 1 1 1 1 1 1 1

문제는 명확하고 직관적이다. 1페이지부터 $N$페이지까지 나열할 때, 숫자가 사용된 수를 각 숫자별로 나타내는 문제.

165라는 숫자를 표기하기 위해선 $[ 1, 5, 6 ]$이 사용된다. 이렇게 1부터 해당 숫자까지의 모든 숫자를 표현하기 위해 사용한 숫자의 수를 0부터 오름차순으로 출력하면 된다.

즉, $N = 5$라고 가정하면, 페이지 배열은 $[ 1, 2, 3, 4, 5 ]$까지 나열된다. 각 숫자가 사용된 수를 표로 나타내면 아래와 같다.

1부터 5까지 나열하는데, 각각 숫자 하나씩 사용했으니 위 처럼 표시할 수 있다. 그렇다면 예제의 11은 어떨까?

$[ 1, 2, 3, \dots, 10, 11 ]$까지 나열된다.

1부터 9까지는 각각 숫자가 하나씩 사용되며, 10은 1과 0이 사용되고, 11은 1이 두 개 사용된다.

위의 표만큼 숫자가 사용됐다. 이해를 위해 $N = 13$일 경우를 하나 더 해보자.

$12 = [ 1, 2 ]$, $13 = [ 1, 3 ]$이 된다. 1 ~ 13에는 11도 포함되기 때문에, 11의 결과에 12, 13의 값을 각각 더해줘도 상관없다.

이 정도면 알고리즘이 원하는 게 무엇인지 이해했으리라 생각한다.

사실 무식하게 접근하면, 그리 어려운 문제는 아니다. 하나하나 반복문 돌려가며 숫자 분해해서 해당하는 숫자의 배열에 집어넣으면 그만이니. 하지만 안타깝게도, 변수 $N$의 최대값은 10억 (다행히 int의 최대값은 넘지 않는다.) 에 육박한다. 그 말인즉는 무식하게 접근하면 안 된다는 의미.

그렇다면 어딘가에 존재하는 규칙성을 발견해서 일반식을 설계해야한다는 뜻인데, 이럴땐 하나하나 나열해보면 알 수 있을 것이다.

규칙성을 찾아보기 위해 20 받고 살짝 더 얹어서 사용된 숫자를 나열해보았다. 어떤 패턴이 보이는 것 같긴 하다.

1. 0은 10의 배수마다 1씩 증가한다.
2. 각 1의 자리마다 해당하는 숫자가 1씩 증가하며, 값은 10의 자릿수 + 1이다.
3. 10의 자릿수는 해당하는 숫자를 1씩 증가시킨다.

그냥 쳐다보면 규칙성을 찾기 좀 어려울 수 있다. 해답은 *0 ~ *9 구간에 있다. 예를 들어, 10 ~ 29까지 나열해보자. 1부터 시작하는 것이 아니라, 임의의 구간 $A ~ B$를 기준으로 알고리즘을 계산한다고 가정하는 것이다.

위 표의 숫자들을 잘 보면, 1의 자리 숫자는 각각 하나씩 사용하는 것을 확인할 수 있다.

이제 좀 규칙성이 눈에 띄기 시작한다. 20 ~ 39와 같은 *0 ~ *9 형태의 범위에선 1의 자리에 해당하는 모든 숫자가 동일하게 사용된다. 10 ~ 19, 20 ~ 29 두 구간이 있으므로 각 구간별로 1씩 모든 숫자가 두 번 사용됐다.

시작 페이지를 $n$, 마지막 페이지를 $N$이라고 가정할 때, 위 규칙을 일반식으로 표현하면 아래와 같다.

$$(N \div 10) - (n \div 10) + 1 = \text{1의 자리에 사용된 각각의 숫자 갯수}$$

따라서 10 ~ 29 범위에서 모든 숫자는 두 번 사용된 것임을 알 수 있다.

문제는 위 식은 1의 자리에서만 적용되는 수식이다. 페이지는 최대 10의 자리까지 존재할 수 있다. 즉, 통용되는 일반식을 구해야한다.

반대로 10의 자리수를 자세히 보자. 1이 10번 사용된다. 만약 100 ~ 199 구간이라면 1은 100개가 사용될 것이고, 1000 ~ 1999 구간이라면 1은 1000개가 사용될 것이다.

쉽게 설명하기 위해 10 ~ 19, 100 ~ 199, 1000 ~ 1999 등 $n0* ~ n9*$ 같은 형태의 구간을 단위 구간이라고 정의하자. 이 때, 해당 구간에서 $n$이 사용되는 갯수는 아래와 같이 정의할 수 있다.

$$((N \div 10) - (n \div 10) + 1) \times \text{p} = \text{각각의 숫자 갯수}$$

• $n$: 구간 시작 값
• $N$: 구간 끝 값
• $p$: 자릿수

이제 구간만 맞으면 호출되는 숫자를 구할 수는 있지만, 아직 제한적이다.

우선, 본 알고리즘에서 시작 값은 1로 고정이다. 끝 값인 $N$ 역시 반드시 199와 같은 단위 구간의 형태로 들어오지도 않는다. 만약 $N = 35$라면 우리는 1 ~ 35 구간에 알고리즘을 적용해야 한다. 구간이 10 ~ 39라면 모를까, 형태가 전혀 다른 구간에는 위 일반식이 적용되지 않는다.

해결 방법은 간단하다. 가늠좌 클리크 조정하듯이 구간에 맞게 값을 더하고 빼서 조정해주면 된다.

1 ~ 35 구간에서, 1의 경우, 1보다 크며 0을 포함한 수 중 가장 가까운 값은 10이다. 따라서, 시작 값은 10까지 증가시키며, 증가시킨 숫자를 카운팅한다. 1부터 9까지 카운팅되므로, 이를 표로 표현하면 아래와 같다.

35의 경우 35보다 작으며 9를 포함한 수 중 가장 가까운 수는 29다. 마찬가지로 마지막 값은 29까지 감소시키며, 감소한 숫자를 카운팅한다. 35부터 30까지 카운팅되므로, 이를 표로 표현하면 아래와 같다.

즉, 초기값은 위 보정값을 더한 배열이며, 이후 계산은 계산된 초기값에 누적한다.

$N = 1999$, $n = 1000$일 때, 1의 자리에 사용된 숫자의 갯수를 구하면 아래와 같다.

$$((1999 / 10) - (1000 / 10) + 1) \times 1 = 100$$

1의 자리에서 각 숫자는 100개씩 사용됐다. 10의 자리에서는 어떨까?

$N$, $n$을 각각 10으로 나누면 10의 자리에 대한 구간을 얻을 수 있다. 나눠진 숫자를 위의 일반식에 적용하면 된다.

$$((199 / 10) - (100 / 10) + 1) \times 10 = 100$$

100의 자리는 $N$, $n$을 각각 100으로 나누어 계산하면 된다.

$$((19 / 10) - (10 / 10) + 1) \times 100 = 100$$

1000의 자리는 $N$, $n$을 각각 1000으로 나누어 계산하면 된다. 그러나 $N = n = 1$이므로, 1에만 1000개가 사용된다.

따라서 1000 ~ 1999 구간은 위와 같이 계산된다.

완벽한 이해를 위해, 위 개념을 토대로 $N = 4153$일 경우의 알고리즘을 계산해보자.

$N = 4153$이므로, 구간은 1 ~ 4153이다.

1보다 큰 수 중 1의 자리가 0인 가장 가까운 수 10까지 이동하며, 이동한 수를 별도로 카운팅한다.

1부터 9까지 이동하여 10에 도착하므로, 1 ~ 9를 별도로 카운팅해준다.

4153보다 작은 수 중 1의 자리가 9인 가장 가까운 수 4149까지 이동하며, 이동한 수를 별도로 카운팅한다.

4153부터 4150까지 이동하여 4149까지 도착하므로, 이를 별도로 카운팅해준다.

일반식을 적용할 수 있는 구간 10 ~ 4149을 구했으니, 일반식을 적용한다.

$$((4149 / 10) - (10 / 10) + 1) \times 1 = 414 - 1 + 1 = 414$$

상위 자릿수 계산을 위해 1의 자리 일반식 구간 4149, 10을 각각 10으로 나눈다.

10의 자리에 대한 구간은 $1 ~ 414$가 된다. 마찬가지로 일반식 적용을 위해 구간을 보정한다. 10의 자리이므로, 1 -> 2로의 이동은 실제로 10 -> 20으로의 이동임에 주의하자.

일반식을 적용할 수 있는 구간 10 ~ 409를 구했으니, 일반식을 적용한다.

$$((409 / 10) - (10 / 10) + 1) \times 10 = (40 - 1 + 1) \times 10 = 400$$

상위 자릿수 계산을 위해 10의 자리 일반식 구간 409, 10을 각각 10으로 나눈다.

100의 자리에 대한 구간은 $1 ~ 40$이 된다. 나머지는 10의 자리 프로세스와 동일하다.

일반식을 적용할 수 있는 구간 10 ~ 39를 구했으니, 일반식을 적용한다.

$$((39 / 10) - (10 / 10) + 1) \times 100 = (3 - 1 + 1) \times 100 = 300$$

상위 자릿수 계산을 위해 100의 자리 일반식 구간 39, 10을 각각 10으로 나눈다.

1000의 자리에 대한 구간은 $1 ~ 3$이 된다.

여기서 문제가 하나 있는데, 마지막 구간에서 일의 자리가 9인 가장 작은 수는 -9다. 음수가 올 수 없으므로, 더 이상의 일반식 연산은 불가능하며, 개별적으로 더해주면 된다.

단계별로 구한 숫자를 정리하여 총합을 표로 나타낸다.

구간 1 ~ 4153에 대한 알고리즘 결과는 위와 같다.

JAVA
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/**
 * 백준 전체 1019 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/28/a1019">1019 풀이</a>
 * @since 2021.06.28 Mon 12:28:50
 */
public class Main
{
    // 숫자 카운트 배열
    private static final int[] COUNTER = new int[10];
    
    /**
     * 메인 함수
     *
     * @param args: [String[]] 매개변수
     *
     * @throws IOException 데이터 입출력 예외
     */
    public static void main(String[] args) throws IOException
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 마지막 페이지
        int N = Integer.parseInt(reader.readLine());
        
        solve(N);
        
        StringBuilder builder = new StringBuilder();
        
        for (int item : COUNTER)
        {
            builder.append(item).append(" ");
        }
        
        writer.write(builder.toString().trim());
        writer.newLine();
        writer.flush();
        
        reader.close();
        writer.close();
    }
    
    /**
     * 알고리즘 동작 함수
     *
     * @param num: [int] 마지막 페이지
     */
    private static void solve(int num)
    {
        // 시작 페이지
        int start = 1;
        
        // 자릿수
        int digit = 1;
        
        while (start <= num)
        {
            // 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소함
            while (num % 10 != 9 && start <= num)
            {
                // 감소한 페이지 별도 카운팅
                count(num, digit);
                
                num--;
            }
            
            // 마지막 페이지가 시작 페이지보다 작을 경우
            if (num < start)
            {
                // 이를 처리하지 않으면 num < 9일 경우 무한루프를 탐
                break;
            }
            
            // 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가함
            while (start % 10 != 0 && start <= num)
            {
                // 증가한 페이지 별도 카운팅
                count(start, digit);
                
                start++;
            }
            
            start /= 10;
            num /= 10;
            
            for (int i = 0; i < 10; i++)
            {
                COUNTER[i] += (num - start + 1) * digit;
            }
            
            // 자릿수 증가
            digit *= 10;
        }
    }
    
    /**
     * 카운트 함수
     *
     * @param num: [int] 대상 숫자
     * @param digit: [int] 자릿수
     */
    private static void count(int num, int digit)
    {
        while (num > 0)
        {
            COUNTER[num % 10] += digit;
            num /= 10;
        }
    }
}

$N = 4153$일 때, 구간을 보정하는 과정에서 4153, 4152와 같은 수를 별도로 카운팅해야한다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 카운트 함수
 *
 * @param num: [int] 대상 숫자
 * @param digit: [int] 자릿수
 */
private static void count(int num, int digit)
{
    while (num > 0)
    {
        counter[num % 10] += digit;
        num /= 10;
    }
}

로직은 어렵지 않다. 4152의 경우 $[ 4, 1, 5, 2 ]$로 이루어져있으므로, 해당하는 숫자에 자릿수만큼 카운팅(1이면 1개, 10이면 10개)하면 된다.

1의 자리는 $4152 \,\,\, \% \,\,\, 10 = 2$와 같이 구할 수 있다. 10의 자리는 4152를 10으로 한 번 나누고 방금의 연산을 다시 진행하면 된다.
100, 1000 등 자릿수만큼 반복하여 계산하면 된다.

JAVA
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * 알고리즘 동작 함수
 *
 * @param num: [int] 마지막 페이지
 */
private static void solve(int num)
{
    // 시작 페이지
    int start = 1;
    
    // 자릿수
    int digit = 1;
    
    while (start <= num)
    {
        // 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소함
        while (num % 10 != 9 && start <= num)
        {
            // 감소한 페이지 별도 카운팅
            count(num, digit);
            
            num--;
        }
        
        // 마지막 페이지가 시작 페이지보다 작을 경우
        if (num < start)
        {
            // 이를 처리하지 않으면 num < 9일 경우 무한루프를 탐
            break;
        }
        
        // 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가함
        while (start % 10 != 0 && start <= num)
        {
            // 증가한 페이지 별도 카운팅
            count(start, digit);
            
            start++;
        }
        
        start /= 10;
        num /= 10;
        
        for (int i = 0; i < 10; i++)
        {
            counter[i] += (num - start + 1) * digit;
        }
        
        // 자릿수 증가
        digit *= 10;
    }
}

시작 페이지는 무조건 1로 고정이다. 시작 페이지가 마지막 페이지보다 커질 때까지 반복한다.

첫 번째 while문에서 마지막 페이지를 1씩 감소시켜 9로 끝나는 구간으로 보정한다. 중간에 조건문이 있는데, 이 처리를 해주지 않으면 num이 9보다 작을 경우 연산 과정에서 start가 num을 초과하지 못해 무한루프를 타게 된다.

두 번째 while문은 1페이지를 1씩 증가시켜 0으로 끝나는 구간으로 보정한다. 보정된 모든 값은 count 메소드를 통해 별도로 카운팅된다.

위 과정을 통해 구간을 맞췄으니, 나머지는 위에 언급한 수식을 적용하고, 이를 반복한다.

• 수학