BOJ 1019

문제 설명

• 문제: 백준 1019

이 문제는 겉보기에는 굉장히 간단한 문제입니다. N을 입력받아, 1부터 N까지 모든 수에 대해 0부터 9까지의 숫자가 몇 번씩 나왔는지를 구하면 됩니다. 입 출력이 간단하고, 언뜻 보면 간단한 반복문을 통해 풀 수 있을 것이라 생각되지만, N의 조건을 잘 살펴봐야 합니다. N이 $10^9$이하의 자연수라는 사실 때문에 $O(N)$보다도 더 빠른 알고리즘이 필요합니다.

사전 지식

이 문제를 푸는 데는 큰 사전 지식을 필요로 하지 않습니다. 다만 문제를 푸는데 도움이 되었던 사실 몇 가지를 짚어보려 합니다. 직관적인 설명을 위해 모든 숫자를 네 자릿수로 고정한 후 설명하겠습니다.

1부터 9999까지 등장하는 모든 숫자를 세기 위해서는 여러 가지 방법을 쓸 수 있지만, 다음과 같은 방법을 사용할 수 있습니다.

0000 부터 9999까지의 모든 수 중에서 각 숫자가 얼마나 나왔는지 셉니다. 0000 부터 0999까지의 모든 수 중에서, 앞에 붙는 0의 갯수를 제외합니다. 즉, 세 자리 이하의 모든 수의 앞에 0을 붙여서, 11과 같은 숫자를 0011로 만듭니다. 그 다음에 모든 숫자를 다 세고, 앞에 붙는 0의 갯수를 다시 빼주는 방식으로 계산하는 것입니다. 번거로워 보이지만 계싼을 훨씬 간단하게 할 수 있습니다.

0000 - 9999

0000부터 9999까지의 수의 갯수는 10,000개이고, 모든 숫자의 자릿수는 네 자릿수이기 때문에, 0부터 9까지 나오는 모든 숫자의 갯수는 총 40,000개입니다. 이 때 0부터 9까지 모든 수가 균등하게 분포되어있으므로, 각 숫자는 총 4,000개씩 나온다고 볼 수 있습니다.

임의의 N자릿수에 대해 일반화 하면, 각 숫자가 $N * 10^{N-1}$ 개씩 나온다는 사실을 알 수 있습니다.

0000 - 0999

0000부터 0999까지 나오는 “앞에 붙는” 0의 갯수를 세면 됩니다. 즉, 0104같은 경우 1의 앞에 오는 0의 갯수만 세면 되고, 이는 1개입니다. 0의 갯수를 세기 위해 다음과 같은 경우들로 나누었습니다.

0100 ~ 0999 : 0이 1개 오는 경우 → 총 900개
0010 ~ 0099 : 0이 2개 오는 경우 → 총 90개
0001 ~ 0009 : 0이 3개 오는 경우 → 총 9개
0000 : 0이 4개 오는 경우 → 총 1개

즉 $1 * 900 + 2 * 90 + 3 * 9 + 4 * 1$ 개만큼 0의 갯수를 빼 주면 됩니다. 이를 임의의 N자릿수에 대해 일반화 하면, 다음과 같습니다.

$$ 1 + \sum_{n = 1}^{N - 1} n * 9 * 10^{N-n-1} $$

접근 방법

이 문제는 2년 전 알고리즘을 처음 배울 때 시도했다가 시간 초과로 실패했던 문제입니다. 그 때 풀었던 방법과 현재 풀었던 방법을 간단하게 비교해 볼 것입니다. 2년 전은 C, 현재의 풀이는 Python3를 이용해 풀었습니다. 두 언어의 속도차이를 감안하면 알고리즘의 차이가 속도에 얼마나 영향을 주는지가 명백합니다.

단순한 재귀 함수

처음에는 N이 얼마나 큰지도, 재귀함수의 호출도 생각하지 않았기 때문에, 아주 짧은 생각으로 재귀함수를 이용해 풀려고 생각했습니다. 반복문을 이용하는 것과 방법적인 차이는 없고, 단순히 1부터 N까지 모든 수를 다 살펴보면서 해당 수에 어떤 숫자가 등장했는지를 살펴보면서 배열에 값을 하나씩 더하는 식입니다.

void cntpage(int n) {
    if (n > 0) {
        int stor = n;
        while (n != 0) {
            number[n % 10]++;
            n /= 10;
		}
        return cntpage(stor - 1);
    }
    return;
}

Tail recursion으로 어떻게든 최적화를 시켜도, 함수 호출만 N번입니다. 각 함수에서 그 수의 자릿수, 즉 logN번 연산이 되기 때문에 시간 복잡도를 $O(NlogN)$으로 볼 수 있습니다. N이 $10^9$라면 시간 내에 풀기는 힘들 것으로 보입니다.

규칙성 찾기

N이 주어졌을때 1부터 N까지 각 수를 조사하는 방법은 너무 비효율적이라고 생각해서, 2장에서 살펴본 사전 지식을 활용해 규칙성을 찾아 문제를 풀어보기로 했습니다.

가장 기본적인 아이디어는 어떤 숫자에 대해, 일의 자리부터 가장 큰 자릿수까지 숫자를 계속 $10^n$단위로 잘라 내면서 자르기 전 수와 현재 수 사이에 나오는 숫자들을 세는 것입니다. 7542라는 수를 예를 들어 보죠.

이 수를 7542 → 7540 → 7500 → 7000 → 0000 으로 깎아 내려 가면서, 두 수 사이에 어떤 숫자가 몇 개 오는지 체크를 하면 됩니다. 이를 코드로 구현하기 위해, 다음과 같이 세 단계로 나누어 생각해 보기로 했습니다.

현재 자릿수보다 높은 자릿수에 나오는 숫자를 센다. 현재 자릿수에 나오는 숫자들을 센다. 현재 자릿수보다 낮은 자릿수에 나오는 숫자들을 센다. 실제 수인 7542를 상기 설명한 과정에 넣어서 생각해 봅시다. 0000 ~ 7542라는 숫자는 다음과 같이 쪼갤 수 있습니다. 여기에서 이하가 아닌 미만으로 한 이유는 후술할 예정입니다.

7542
7540 이상 7542 미만 사이의 모든 숫자
7500 이상 7540 미만 사이의 모든 숫자
7000 이상 7500 미만 사이의 모든 숫자
0000 이상 7000 미만 사이의 모든 숫자

• 7540 이상 7542 미만에서 등장하는 모든 숫자는 다음과 같이 계산합니다.

현재 자릿수보다 높은 754는 고정으로 등장하므로, 현재 단계에 나타난 수 만큼 7, 5, 4가 나타났습니다. 여기서는 두 수 사이에 2개가 있으므로 각 숫자가 2번 나타납니다. 현재 자릿수에 나올 수 있는 숫자는 0, 1이고 이는 1($= 10^0$)번씩 나타납니다. 현재 자릿수보다 낮은 자릿수의 숫자는 나타나지 않습니다.

• 7500 이상 7540 미만에서 등장하는 모든 숫자는 다음과 같이 계산합니다.

현재 자릿수보다 높은 75는 고정으로 등장하므로, 현재 단계에 나타난 수 만큼 7, 5가 나타났습니다. 여기서는 두 수 사이에 40개가 있으므로 각 숫자가 40번 나타납니다. 현재 자릿수에 나오는 숫자는 0, 1, 2, 3이고 이는 이는 10($= 10^1$)번씩 나타납니다. 현재 자릿수보다 낮은 자릿수의 숫자 0 부터 9가 총 4번(현재 자릿수가 총 0, 1, 2, 3으로 4개 나올 수 있으므로) 나타납니다.

• 7000 이상 7500 미만에서 등장하는 모든 숫자는 다음과 같이 계산합니다.

현재 자릿수보다 높은 7은 고정으로 등장하므로, 현재 단계에 나타난 수 만큼 7이 나타났다고 표시해 주면 됩니다. 여기서는 두 수 사이에 500개가 있으므로 7번 나타납니다. 현재 자릿수에 나오는 숫자는 0, 1, 2, 3, 4이고 이는 이는 100($= 10^2$)번씩 나타납니다. 현재 자릿수보다 낮은 자릿수의 숫자 00 부터 99가 총 5번(현재 자릿수가 총 0, 1, 2, 3, 4로 5개 나올 수 있으므로) 나타납니다.

• 0000 이상 7000 미만에서 등장하는 모든 숫자는 다음과 같이 계산합니다.

현재 자릿수보다 높은 자릿수의 숫자는 나타나지 않습니다. 현재 자릿수에 나오는 숫자는 0, 1, …, 6이고 이는 이는 1000($= 10^3$)번씩 나타납니다. 현재 자릿수보다 낮은 자릿수의 숫자 000 부터 999가 총 7번(현재 자릿수가 총 0, 1 …, 6 으로 7개 나올 수 있으므로) 나타납니다. 000…0 부터 999…9까지 각 숫자가 몇 개 나오는지는 2.1장에서 미리 계산해 두었으므로 그 값을 이용하면 현재 자릿수보다 낮은 자릿수의 숫자가 몇 개 나오는지 쉽게 알 수 있습니다. 이후 2.2장에서 살펴본 바와 같이, 앞에 불필요하게 붙은 0의 갯수를 제외해 주면 됩니다.

코드 설명

커팅된 수를 이용한 계산

등장할 수 있는 모든 자릿수에 대해, $10^n$으로 나눈 나머지를 제거한 수를 만듭니다. 이 수를 커팅된 수라고 칭하겠습니다. 이후 현재 수와 커팅된 수 사이에 몇 개의 숫자가 있는 지를 계산합니다. 정확히는 위에 설명한 바와 같이 커팅된 수 이상 현재 수 미만으로 계산합니다. 원래 수가 7540, 커팅된 수가 7500이면 두 수 사이에는 40개의 숫자가 존재합니다.

만약 두 수 사이에 수가 없다면, 즉 , 커팅된 수와 원래 수가 같다면, 두 수 사이의 숫자를 셀 필요가 없으므로 현재 자릿수에서는 계산을 하지 않습니다.

# In this for loop, by repeatedly cutting the number, it counts digit
for cur_exp in range(max_exp):

	cut_number = number - (number % exp_of_10[cur_exp + 1])
	cnts = (number - cut_number)

	if cnts == 0:
		continue

upper_numbers는 현재 자릿수보다 위에 있는 숫자, 즉 3장에서 말한 고정된 숫자들을 의미합니다. 예를 들어, 7540에서 7500으로 커팅했다면, 7과 5는 고정되어 있으므로 이들을 의미합니다. 반면 cur_number은 현재 자릿수에 위치한 숫자를 의미합니다. 즉, 7540에서 7500으로 줄어들면서 사라진 “4"를 의미합니다.

첫 번째로 고정된 숫자들에 대해서 셈을 합니다. 이 숫자들은 두 수 사이의 숫자의 갯수만큼 나오므로, 아까 계산했던 cnts 만큼 더해주면 됩니다. cur_number가 4라면, 0, 1, 2, 3이 현재 자릿수에 등장할 것입니다. 이 숫자들이 $10^{현재자릿수 - 1}$ 만큼 나오기 때문에, 두 번째에는 이것을 등장하는 각 숫자에 더해주면 됩니다.

# The digits that have higher exponent than current exponent
upper_numbers = number_list[:max_exp - cur_exp - 1]

# The digit of current exponent
cur_number = number_list[max_exp - cur_exp - 1]

for upper_number in upper_numbers:
	digit_list[upper_number] += cnts

for und_cur_number in range(cur_number):
	digit_list[und_cur_number] += exp_of_10[cur_exp]

그 다음은 현재 자릿수 미만의 자릿수에 나오는 숫자들을 세어 주면 됩니다. 만약 현재 자릿수가 일의 자리라면, 현재 자릿수보다 아랫 자리수는 없으므로 무시하면 되고, 현재 자릿수가 십의 자리 이상일 때를 살펴봅시다.

2.1장에서 살펴본 바와 같이 000..0 부터 999..9까지의 등장을 하는 각 숫자의 갯수를 모든 숫자에 더해주면 됩니다. 여기서 주의할 점은, 아랫자릿수에 나오는 이 수들은 현재 자릿수에 나올 수 있는 숫자만큼 나오니, cur_number 만큼 곱해줘서 더해야 겠죠. list_sum 함수는 첫 리스트에 두번째 리스트의 값을 elementwise하게 더하는 함수입니다.

현재 수를 커팅된 수로 저장하고 반복문을 다시 시행하면 됩니다. 여기에서 아까 이상과 미만으로 한 이유가 나오는데, 이상과 이하로 하면 같은 수가 반복해서 세어지기 때문입니다.

# If the current exponent is not zero, then lower exponent must be count
if cur_exp != 0:
	list_sum(digit_list, [digits_under_exp_of_10[cur_exp - 1] * cur_number] * 10)

# Cut the number and repeat this procedure
number = cut_number

앞에 붙은 0 제거

for문을 진행한 후에는 2.2장에서 설명한 바와 같이 앞에 붙는 불필요한 0을 제거하는 과정을 진행했습니다. 2.2장에서 계산한 수식에 맞게 0의 갯수를 세어준 다음 그만큼 리스트에서 빼 주었습니다. zero_under_exp_of_10는 2.2의 수식을 N에 따라 값을 저장해 둔 배열입니다.

# Delete leading zeros
leading_zero = 0

for del_exp in range(max_exp):
    leading_zero += ((del_exp + 1) * (zero_under_exp_of_10[max_exp - del_exp - 1]))

digit_list[0] -= leading_zero

결론

아주 오랫동안 고민해서 푼 문제이지만, 정답과는 거리가 있고 시행 착오를 많이 겪은 문제입니다. 정답에 가까운 풀이는 재귀를 이용한 풀이를 참고하시면 될 것 같습니다. 이런 풀이가 있구나 정도로만 여기시면 될 것 같습니다.

코드 원본은 여기를 참고해 주시면 됩니다.

References

1. 백준 1019번 풀이
2. 백준 1019