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

⏰ 2021-06-28 (월) 12:28:50

screener
시리즈 모아보기
백준 알고리즘

21 / 23

Table of Contents

  • 1. 책 페이지

























책 페이지

랭크사용 언어
JAVA

🔗 🔗 전체 1019번 문제

조건

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

문제

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

입력

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

출력

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

케이스

예제 1

  • 입력

TC

1
11
  • 출력

TC

1
1 4 1 1 1 1 1 1 1 1

풀이

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

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

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

0123456789
0111110000

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

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

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

0123456789
1411111111

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

0123456789
1411111111

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

0123456789
1622111111

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

🔎규칙 찾아보기

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

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

N0123456789
10100000000
20110000000
30111000000
40111100000
50111110000
60111111000
70111111100
80111111110
90111111111
101211111111
111411111111
121521111111
131622111111
141722211111
151822221111
161922222111
1711022222211
1811122222221
1911222222222
2021232222222
2121342222222
2221362222222
2321373222222

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

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

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

숫자 현황
10111213141516171819
20212223242526272829

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

1의 자리에서의 규칙

숫자 현황
10111213141516171819
20212223242526272829

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

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

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

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

p의 자리에서의 규칙

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

숫자 현황
10111213141516171819
20212223242526272829

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

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

((N÷10)(n÷10)+1)×p=각각의 숫자 갯수((N \div 10) - (n \div 10) + 1) \times \text{p} = \text{각각의 숫자 갯수}
  • nn: 구간 시작 값
  • NN: 구간 끝 값
  • pp: 자릿수

구간 보정하기

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

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

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

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

0123456789
0111111111

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

0123456789
1117110000

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

0123456789
0111111111
1117110000
1228221111

자릿수 보정하기

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

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

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

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

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

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

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

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

pp0123456789
1100100100100100100100100100100
10100100100100100100100100100100
100100100100100100100100100100100
10000100000000000
3001300300300300300300300300300

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

📃일반식 적용하기

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

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

시작 페이지 구간 보정하기

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

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

구분0123456789
1 ~ 90111111111

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

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

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

구분0123456789
41530101110000
41520110110000
41510200110000
41501100110000

1의 자리 일반식 적용

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

((4149/10)(10/10)+1)×1=4141+1=414((4149 / 10) - (10 / 10) + 1) \times 1 = 414 - 1 + 1 = 414
구분0123456789
1의 자리414414414414414414414414414414

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

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

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

구분0123456789
1 ~ 90101010101010101010
구분0123456789
414010002000000
4130100101000000
4120101001000000
411020001000000
4101010001000000

10의 자리 일반식 적용

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

((409/10)(10/10)+1)×10=(401+1)×10=400((409 / 10) - (10 / 10) + 1) \times 10 = (40 - 1 + 1) \times 10 = 400
구분0123456789
10의 자리400400400400400400400400400400

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

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

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

구분0123456789
1 ~ 90100100100100100100100100100
구분0123456789
4010000010000000

100의 자리 일반식 적용

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

((39/10)(10/10)+1)×100=(31+1)×100=300((39 / 10) - (10 / 10) + 1) \times 100 = (3 - 1 + 1) \times 100 = 300
구분0123456789
10의 자리300300300300300300300300300300

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

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

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

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

구분0123456789
1 ~ 30100010001000000000

총합 계산하기

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

구분0123456789
1 ~ 90111111111
41530101110000
41520110110000
41510200110000
41501100110000
1의 자리414414414414414414414414414414
1 ~ 90101010101010101010
414010002000000
4130100101000000
4120101001000000
411020001000000
4101010001000000
10의 자리400400400400400400400400400400
1 ~ 90100100100100100100100100100
4010000010000000
10의 자리300300300300300300300300300300
1 ~ 30100010001000000000
총합1225229022362236138912291225122512251225

구간 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=4153N = 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][ 4, 1, 5, 2 ]로 이루어져있으므로, 해당하는 숫자에 자릿수만큼 카운팅(1이면 1개, 10이면 10개)하면 된다.

1의 자리는 4152%10=24152 \,\,\, \% \,\,\, 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보다 작을 경우 연산 과정에서 startnum을 초과하지 못해 무한루프를 타게 된다.

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

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

분류

  • 수학

🏷️ 태그
# 백준
# 알고리즘
# JAVA(자바)
# GOLD
# GOLD I

읽어주셔서 고마워요!

도움이 되셨다면, 공감이나 댓글을 달아주시는 건 어떤가요?

블로그 운영에 큰 힘이 됩니다.

https://hits.seeyoufarm.com/api/count/incr/badge.svg?count_bg=%23484848&icon=react.svg&icon_color=dodgerblue&title=view&title_bg=%23242424&url=https%3A%2F%2Fblog.itcode.dev%2Fposts%2F2021%2F06%2F28%2Fa1019