책 페이지 🔗

랭크	사용 언어

🔗 전체 1019번 문제

조건 🔗

문제 🔗

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

입력 🔗

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

출력 🔗

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

케이스 🔗

예제 1 🔗

• 입력

0
11

• 출력

0
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부터 시작하는 것이 아니라, 임의의 구간 $AB$를 기준으로 알고리즘을 계산한다고 가정하는 것이다.

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

1의 자리에서의 규칙 🔗

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

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

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

p의 자리에서의 규칙 🔗

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

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

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

• $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의 자리에 사용된 숫자의 갯수를 구하면 아래와 같다.

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

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

100의 자리는 $N$, $n$을 각각 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까지 도착하므로, 이를 별도로 카운팅해준다.

1의 자리 일반식 적용 🔗

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

10의 자리 구간 계산 및 보정하기 🔗

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

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

10의 자리 일반식 적용 🔗

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

100의 자리 구간 계산 및 보정하기 🔗

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

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

100의 자리 일반식 적용 🔗

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

1000의 자리 구간 계산 및 보정하기 🔗

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

1000의 자리에 대한 구간은 $13$이 된다.

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

총합 계산하기 🔗

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

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

전체 소스 🔗

0
import java.io.BufferedReader;
1
import java.io.BufferedWriter;
2
import java.io.IOException;
3
import java.io.InputStreamReader;
4
import java.io.OutputStreamWriter;
5

6
/**
7
 * 백준 전체 1019 문제 알고리즘 클래스
8
 *
9
 * @author RWB
10
 * @see <a href="https://blog.itcode.dev/posts/2021/06/28/a1019">1019 풀이</a>
11
 * @since 2021.06.28 Mon 12:28:50
12
 */
13
public class Main
14
{
15
    // 숫자 카운트 배열
16
    private static final int[] COUNTER = new int[10];
17
    
18
    /**
19
     * 메인 함수
20
     *
21
     * @param args: [String[]] 매개변수
22
     *
23
     * @throws IOException 데이터 입출력 예외
24
     */
25
    public static void main(String[] args) throws IOException
26
    {
27
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
28
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
29
        
30
        // 마지막 페이지
31
        int N = Integer.parseInt(reader.readLine());
32
        
33
        solve(N);
34
        
35
        StringBuilder builder = new StringBuilder();
36
        
37
        for (int item : COUNTER)
38
        {
39
            builder.append(item).append(" ");
40
        }
41
        
42
        writer.write(builder.toString().trim());
43
        writer.newLine();
44
        writer.flush();
45
        
46
        reader.close();
47
        writer.close();
48
    }
49
    
50
    /**
51
     * 알고리즘 동작 함수
52
     *
53
     * @param num: [int] 마지막 페이지
54
     */
55
    private static void solve(int num)
56
    {
57
        // 시작 페이지
58
        int start = 1;
59
        
60
        // 자릿수
61
        int digit = 1;
62
        
63
        while (start <= num)
64
        {
65
            // 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소함
66
            while (num % 10 != 9 && start <= num)
67
            {
68
                // 감소한 페이지 별도 카운팅
69
                count(num, digit);
70
                
71
                num--;
72
            }
73
            
74
            // 마지막 페이지가 시작 페이지보다 작을 경우
75
            if (num < start)
76
            {
77
                // 이를 처리하지 않으면 num < 9일 경우 무한루프를 탐
78
                break;
79
            }
80
            
81
            // 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가함
82
            while (start % 10 != 0 && start <= num)
83
            {
84
                // 증가한 페이지 별도 카운팅
85
                count(start, digit);
86
                
87
                start++;
88
            }
89
            
90
            start /= 10;
91
            num /= 10;
92
            
93
            for (int i = 0; i < 10; i++)
94
            {
95
                COUNTER[i] += (num - start + 1) * digit;
96
            }
97
            
98
            // 자릿수 증가
99
            digit *= 10;
100
        }
101
    }
102
    
103
    /**
104
     * 카운트 함수
105
     *
106
     * @param num: [int] 대상 숫자
107
     * @param digit: [int] 자릿수
108
     */
109
    private static void count(int num, int digit)
110
    {
111
        while (num > 0)
112
        {
113
            COUNTER[num % 10] += digit;
114
            num /= 10;
115
        }
116
    }
117
}

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

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

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

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

0
/**
1
 * 알고리즘 동작 함수
2
 *
3
 * @param num: [int] 마지막 페이지
4
 */
5
private static void solve(int num)
6
{
7
    // 시작 페이지
8
    int start = 1;
9
    
10
    // 자릿수
11
    int digit = 1;
12
    
13
    while (start <= num)
14
    {
15
        // 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소함
16
        while (num % 10 != 9 && start <= num)
17
        {
18
            // 감소한 페이지 별도 카운팅
19
            count(num, digit);
20
            
21
            num--;
22
        }
23
        
24
        // 마지막 페이지가 시작 페이지보다 작을 경우
25
        if (num < start)
26
        {
27
            // 이를 처리하지 않으면 num < 9일 경우 무한루프를 탐
28
            break;
29
        }
30
        
31
        // 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가함
32
        while (start % 10 != 0 && start <= num)
33
        {
34
            // 증가한 페이지 별도 카운팅
35
            count(start, digit);
36
            
37
            start++;
38
        }
39
        
40
        start /= 10;
41
        num /= 10;
42
        
43
        for (int i = 0; i < 10; i++)
44
        {
45
            counter[i] += (num - start + 1) * digit;
46
        }
47
        
48
        // 자릿수 증가
49
        digit *= 10;
50
    }
51
}

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

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

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

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

분류 🔗

• 수학