𝝅번째 알파카의 개발 낙서장

screen

[백준 / JAVA] 백준 알고리즘 1019번 책 페이지

posts

알고리즘

시리즈 톺아보기

백준 알고리즘

백준 알고리즘
count

책 페이지 🔗

랭크 사용 언어
image JAVA

🔗 전체 1019번 문제

조건 🔗

시간제한 메모리 제한
2초 128MB

문제 🔗

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

입력 🔗

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

출력 🔗

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

케이스 🔗

예제 1 🔗

  • 입력

TC

011
  • 출력

TC

01 4 1 1 1 1 1 1 1 1

풀이 🔗

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

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

즉, 라고 가정하면, 페이지 배열은 까지 나열된다. 각 숫자가 사용된 수를 표로 나타내면 아래와 같다.

0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 0 0 0 0

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

까지 나열된다.

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

0 1 2 3 4 5 6 7 8 9
1 4 1 1 1 1 1 1 1 1

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

0 1 2 3 4 5 6 7 8 9
1 4 1 1 1 1 1 1 1 1

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

0 1 2 3 4 5 6 7 8 9
1 6 2 2 1 1 1 1 1 1

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

🔎규칙 찾아보기 🔗

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

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

N 0 1 2 3 4 5 6 7 8 9
1 0 1 0 0 0 0 0 0 0 0
2 0 1 1 0 0 0 0 0 0 0
3 0 1 1 1 0 0 0 0 0 0
4 0 1 1 1 1 0 0 0 0 0
5 0 1 1 1 1 1 0 0 0 0
6 0 1 1 1 1 1 1 0 0 0
7 0 1 1 1 1 1 1 1 0 0
8 0 1 1 1 1 1 1 1 1 0
9 0 1 1 1 1 1 1 1 1 1
10 1 2 1 1 1 1 1 1 1 1
11 1 4 1 1 1 1 1 1 1 1
12 1 5 2 1 1 1 1 1 1 1
13 1 6 2 2 1 1 1 1 1 1
14 1 7 2 2 2 1 1 1 1 1
15 1 8 2 2 2 2 1 1 1 1
16 1 9 2 2 2 2 2 1 1 1
17 1 10 2 2 2 2 2 2 1 1
18 1 11 2 2 2 2 2 2 2 1
19 1 12 2 2 2 2 2 2 2 2
20 2 12 3 2 2 2 2 2 2 2
21 2 13 4 2 2 2 2 2 2 2
22 2 13 6 2 2 2 2 2 2 2
23 2 13 7 3 2 2 2 2 2 2

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

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

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

숫자 현황
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

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

1의 자리에서의 규칙 🔗

숫자 현황
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

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

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

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

p의 자리에서의 규칙 🔗

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

숫자 현황
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

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

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

  • : 구간 시작 값
  • : 구간 끝 값
  • : 자릿수

구간 보정하기 🔗

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

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

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

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

0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1

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

0 1 2 3 4 5 6 7 8 9
1 1 1 7 1 1 0 0 0 0

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

0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1
1 1 1 7 1 1 0 0 0 0
1 2 2 8 2 2 1 1 1 1

자릿수 보정하기 🔗

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

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

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

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

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

0 1 2 3 4 5 6 7 8 9
1 100 100 100 100 100 100 100 100 100 100
10 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100
1000 0 1000 0 0 0 0 0 0 0 0
300 1300 300 300 300 300 300 300 300 300

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

📃일반식 적용하기 🔗

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

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

시작 페이지 구간 보정하기 🔗

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

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

구분 0 1 2 3 4 5 6 7 8 9
1 ~ 9 0 1 1 1 1 1 1 1 1 1

마지막 페이지 구간 보정하기 🔗

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

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

구분 0 1 2 3 4 5 6 7 8 9
4153 0 1 0 1 1 1 0 0 0 0
4152 0 1 1 0 1 1 0 0 0 0
4151 0 2 0 0 1 1 0 0 0 0
4150 1 1 0 0 1 1 0 0 0 0

1의 자리 일반식 적용 🔗

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

구분 0 1 2 3 4 5 6 7 8 9
1의 자리 414 414 414 414 414 414 414 414 414 414

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

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

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

구분 0 1 2 3 4 5 6 7 8 9
1 ~ 9 0 10 10 10 10 10 10 10 10 10
구분 0 1 2 3 4 5 6 7 8 9
414 0 10 0 0 20 0 0 0 0 0
413 0 10 0 10 10 0 0 0 0 0
412 0 10 10 0 10 0 0 0 0 0
411 0 20 0 0 10 0 0 0 0 0
410 10 10 0 0 10 0 0 0 0 0

10의 자리 일반식 적용 🔗

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

구분 0 1 2 3 4 5 6 7 8 9
10의 자리 400 400 400 400 400 400 400 400 400 400

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

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

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

구분 0 1 2 3 4 5 6 7 8 9
1 ~ 9 0 100 100 100 100 100 100 100 100 100
구분 0 1 2 3 4 5 6 7 8 9
40 100 0 0 0 100 0 0 0 0 0

100의 자리 일반식 적용 🔗

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

구분 0 1 2 3 4 5 6 7 8 9
10의 자리 300 300 300 300 300 300 300 300 300 300

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

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

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

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

구분 0 1 2 3 4 5 6 7 8 9
1 ~ 3 0 1000 1000 1000 0 0 0 0 0 0

총합 계산하기 🔗

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

구분 0 1 2 3 4 5 6 7 8 9
1 ~ 9 0 1 1 1 1 1 1 1 1 1
4153 0 1 0 1 1 1 0 0 0 0
4152 0 1 1 0 1 1 0 0 0 0
4151 0 2 0 0 1 1 0 0 0 0
4150 1 1 0 0 1 1 0 0 0 0
1의 자리 414 414 414 414 414 414 414 414 414 414
1 ~ 9 0 10 10 10 10 10 10 10 10 10
414 0 10 0 0 20 0 0 0 0 0
413 0 10 0 10 10 0 0 0 0 0
412 0 10 10 0 10 0 0 0 0 0
411 0 20 0 0 10 0 0 0 0 0
410 10 10 0 0 10 0 0 0 0 0
10의 자리 400 400 400 400 400 400 400 400 400 400
1 ~ 9 0 100 100 100 100 100 100 100 100 100
40 100 0 0 0 100 0 0 0 0 0
10의 자리 300 300 300 300 300 300 300 300 300 300
1 ~ 3 0 1000 1000 1000 0 0 0 0 0 0
총합 1225 2290 2236 2236 1389 1229 1225 1225 1225 1225

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

전체 소스 🔗

JAVA

0import java.io.BufferedReader;
1import java.io.BufferedWriter;
2import java.io.IOException;
3import java.io.InputStreamReader;
4import 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 */
13public 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}

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

JAVA

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

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

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

JAVA

0/**
1 * 알고리즘 동작 함수
2 *
3 * @param num: [int] 마지막 페이지
4 */
5private 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보다 작을 경우 연산 과정에서 startnum을 초과하지 못해 무한루프를 타게 된다.

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

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

분류 🔗

  • 수학