1019번: 책 페이지
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
www.acmicpc.net
문제 내용은 한번 읽으면 모두 파악할 수 있을정도로 간단하다.
그런데 난이도는 골드 1 티어로 생각보다 높은편에 속한다.
1. 헤딩
#include <iostream>
#include <string>
int N;
long long zero = 0;
long long one = 0;
long long two = 0;
long long three = 0;
long long four = 0;
long long five = 0;
long long six = 0;
long long seven = 0;
long long eight = 0;
long long nine = 0;
int main()
{
std::cin >> N;
for (int i = 1; i <= N; ++i)
{
std::string str = std::to_string(i);
for(auto digit : str)
{
switch (digit)
{
case '0':
++zero;
break;
case '1':
++one;
break;
case '2':
++two;
break;
case '3':
++three;
break;
case '4':
++four;
break;
case '5':
++five;
break;
case '6':
++six;
break;
case '7':
++seven;
break;
case '8':
++eight;
break;
case '9':
++nine;
break;
}
}
}
printf("%lld %lld %lld %lld %lld %lld %lld %lld %lld", zero, one, two, three, four, five, six, seven, eight, nine);
}누구나 생각할 수 있을 법한 간단한 원리를 토대로 작성 하였는데,
문제에서 언급된
예제입력 5번을 실행할 경우 10분 이상 시간이 소요되어
실행시간 2초 조건을 무조건 초과할 수 밖에 없었다.
때문에 다른 효율적인 방안을 생각하기 시작했다.
2. 수정한 소스코드
예측되는 문제점은 int -> std::string -> char 로 변환하는 부분에서 속도 저하 문제가 존재할 것이라고 예측 하였다.
때문에 가능한 변환하지 않고, 자릿수별로 나눠 연산처리 하는 방법을 적용해 보았다.
#include <iostream>
#include <math.h>
#include <string>
int N;
long long zero = 0;
long long one = 0;
long long two = 0;
long long three = 0;
long long four = 0;
long long five = 0;
long long six = 0;
long long seven = 0;
long long eight = 0;
long long nine = 0;
int main()
{
std::cin >> N;
for (int i = 1; i <= N; ++i)
{
int temp = i;
int digit;
while (temp != 0)
{
digit = temp % 10;
temp = temp / 10;
switch (digit)
{
case 0:
++zero;
break;
case 1:
++one;
break;
case 2:
++two;
break;
case 3:
++three;
break;
case 4:
++four;
break;
case 5:
++five;
break;
case 6:
++six;
break;
case 7:
++seven;
break;
case 8:
++eight;
break;
case 9:
++nine;
break;
}
}
}
printf("%lld %lld %lld %lld %lld %lld %lld %lld %lld", zero, one, two, three, four, five, six, seven, eight, nine);
}수정한 결과, 전에 비해 연산시간이 대폭 줄어들었다.
그럼에도 불구하고 여전히 예제입력 5번값인
543212345를 입력하면 계산시간은 40초 남짓이 나왔다.
이쯤되어 드는 생각은, 단순 코드 개선으로 속도를 개선하긴 힘들다는 것이다.
근본적인 수학 개념에서 개선점을 찾아야 했다.
3. 규칙성을 찾아보자.
이 문제는 '책' 에 관련된 문제이므로 좀 더 직관적으로 1 부터 시작해 보면 각 숫자 등장 빈도는 다음과 같다.
10,000 : 2893 4001 4000 4000 4000 4000 4000 4000 4000 4000
20,000 : 6893 18000 8001 8000 8000 8000 8000 8000 8000 8000
30,000 : 10893 22000 22000 12001 12000 12000 12000 12000 12000 12000
40,000 : 14893 26000 26000 26000 16001 16000 16000 16000 16000 16000
50,000 : 18893 30000 30000 30000 30000 20001 20000 20000 20000 20000
60,000 : 22893 34000 34000 34000 34000 34000 24001 24000 24000 24000
70,000 : 26893 38000 38000 38000 38000 38000 38000 28001 28000 28000
80,000 : 30893 42000 42000 42000 42000 42000 42000 42000 32001 32000
90,000 : 34893 46000 46000 46000 46000 46000 46000 46000 46000 36001
100,000 : 38894 50001 50000 50000 50000 50000 50000 50000 50000 50000
3-1) 한자리수가 아니며, 추출하려는 수가 F보다 크다면
먼저 한가지 규칙성을 찾을 수 있는데
여기서 첫번째 자리의 숫자를 $F$, 자리수를 $B$, 해당하는 수($F \times 10^{B-2}$)를 $N$ 이라고 지칭하면
10,000 처럼 첫번째 자리수만 할당되고, 뒤의 모든 자리의 수가 0 일 경우
첫번째 자리수를 초과하는 숫자('2' 이상)부터 빈도수가 $N/10 \times (B-1)$ 이다.
즉
if ($Y > F$ and $B \neq 1$ and $N = F \times 10^{B-2}$) 조건에서 Y 를 구하고자 한다면
$$\large Y = {N \over 10} \times (B-1)$$
라는 공식이 성립한다.
즉 50,000 까지 반복했을때 6 이상의 숫자가 얼마나 나오냐?
\begin{flalign}
Y &= {10 \over 50,000} \times (5 - 1)\\
Y &= 5,000 \times 4\\
Y &= 20,000
\end{flalign}
600 까지 반복했을 때 7 이상의 숫자가 얼마나 나오냐?
\begin{flalign}
Y &= {10 \over 600} \times (3 - 1)\\
Y &= 60 \times 2\\
Y &= 120
\end{flalign}
이쯤에서 알 수 있는 사실은 $F \times 10^{B-2}$ 일 때 F 에 해당하는 수는
$N / 10 \times (B-1) + 1$ 만큼 +1 되어 나온다는 사실이다.
3-2) 한자리수가 아니며, 추출하려는 수가 F보다 작다면
if ($Y < F$ and $B \neq 1$ and $N = F \times 10^{B-2}$) 조건에서 $Y$를 구하고자 한다면
$$\large Y = ((F + 10) \times 10^{B-2} + F \times 10^{B-2} \times (B-2))$$
공식이 성립한다.
즉 50,000 까지 반복할 때 '4' 라는 숫자는 아래와 같이 도출된다.
\begin{flalign}
Y &= ((5 + 10) \times 10^{3} + 5 \times 10^{3} \times 3)\\
Y &= (15 \times 1,000) + (5 \times 1,000 \times 3)\\
Y &= 15,000 + 15,000 \\
Y &= 30,000
\end{flalign}
또한 만약 4,000,000 까지 반복하는 경우 '3' 이라는 숫자는 아래와 같이 도출된다.
\begin{flalign}
Y &= ((4 + 10) \times 10^{5} + 4 \times 10^{5} \times 5)\\
Y &= (14 \times 100,000) + (4 \times 100,000 \times 5)\\
Y &= 1,400,000 + 2,000,000\\
Y &= 3,400,000
\end{flalign}
80 까지 반복하는 경우 아래와 같이 도출된다.
\begin{flalign}
Y &= ((8 + 10) \times 10^{0} + 8 \times 10^{0} \times 0)\\
Y &= (18 \times 1) + (8 \times 1 \times 0)\\
Y &= 18 + 0\\
Y &= 18
\end{flalign}
한 자리수일 경우에는 $(B == 1)$
0을 제외하고 N 미만의 수들 모두 1이 나온다.
3-3) $F \times 10^{B-2}$ 일 때 0 의 개수
10 : 1 2 1 1 1 1 1 1 1 1
100 : 11 21 20 20 20 20 20 20 20 20
1000 : 192 301 300 300 300 300 300 300 300 300
10000 : 2893 4001 4000 4000 4000 4000 4000 4000 4000 4000
100000 : 38894 50001 50000 50000 50000 50000 50000 50000 50000 50000
10 : 1 2 1 1 1 1 1 1 1 1
20 : 2 12 3 2 2 2 2 2 2 2
30 : 3 13 13 4 3 3 3 3 3 3
40 : 4 14 14 14 5 4 4 4 4 4
50 : 5 15 15 15 15 6 5 5 5 5
100 : 11 21 20 20 20 20 20 20 20 20
200 : 31 140 41 40 40 40 40 40 40 40
300 : 51 160 160 61 60 60 60 60 60 60
400 : 71 180 180 180 81 80 80 80 80 80
500 : 91 200 200 200 200 101 100 100 100 100
1000 : 192 301 300 300 300 300 300 300 300 300
2000 : 492 1600 601 600 600 600 600 600 600 600
3000 : 792 1900 1900 901 900 900 900 900 900 900
4000 : 1092 2200 2200 2200 1201 1200 1200 1200 1200 1200
5000 : 1392 2500 2500 2500 2500 1501 1500 1500 1500 1500
10000 : 2893 4001 4000 4000 4000 4000 4000 4000 4000 4000
20000 : 6893 18000 8001 8000 8000 8000 8000 8000 8000 8000
30000 : 10893 22000 22000 12001 12000 12000 12000 12000 12000 12000
40000 : 14893 26000 26000 26000 16001 16000 16000 16000 16000 16000
50000 : 18893 30000 30000 30000 30000 20001 20000 20000 20000 20000
여러 검색을 통해 0 의 빈도수가 아래의 규칙성을 가진다는것을 파악했다.
참고로 $(F-1) \cdots$ 부터는 직접 공식을 찾아냈다.
$$\large Y = (B-2) \times 10^{B-2} + (B-2) - {10^{B-2} -1 \over 9} + 1 + (F-1) \times (B-1) \times 10^{B-2}$$
만약 100 일 경우
\begin{flalign}
Y &= (3-2) \times 10^{3-2} + (3-2) - {10^{3-2} - 1 \over 9} + 1 + (1-1) \times (3-1) \times 10^{3-2}\\
Y &= 1 \times 10^{1} + 1 - {10^{1} - 1 \over 9} + 1 + (0) \times (2) \times 10^{1}\\
Y &= 1 \times 10^{1} + 1 - 1 + 1 + 0\\
Y &= 10 + 1 - 1 + 1 + 0\\
Y &= 11\\
\end{flalign}
만약 600,000 일 경우
\begin{flalign}
Y &= (6-2) \times 10^{6-2} + (6-2) - {10^{6-2} - 1 \over 9} + 1 + (6-1) \times (6-1) \times 10^{6-2}\\
Y &= 4 \times 10^{4} + 4 - {10^{4} - 1 \over 9} + 1 + (5) \times (5) \times 10^{4}\\
Y &= 40000 + 4 - 1111 + 1 + 250,000\\
Y &= 288,894\\
\end{flalign}
4. 보정
그러나 이러한 접근방식은 문제가 있다.
10000 : 2893 4001 4000 4000 4000 4000 4000 4000 4000 4000
1000 : 192 301 300 300 300 300 300 300 300 300
11000 : 4192 5302 4300 4300 4300 4300 4300 4300 4300 4300
11,000 의 각 숫자들의 빈도수 = 10,000 빈도수 + 1,000 빈도수 라는 추측을 통해 계산할 수 있을거라 생각했지만
잘 살펴보면 2893 + 192 는 4,192가 아닌걸 알 수 있다.
이는 10,001 과 1,001 의 괴리 차이에서 발생한다.
10,001 ... 은 0의 개수가 더 많은 반면 1,001 에서는 0의 개수가 누락되기 때문이다.
이것까지 공식을 정리하기 위해서는 새로운 논리가 필요하다.
4-1. 예제 - 132
쉽게 132 라는 숫자부터 시작하자.
100 : 11 21 20 20 20 20 20 20 20 20
30 : 3 13 13 4 3 3 3 3 3 3
2 : 0 1 1 0 0 0 0 0 0 0
----------------------------------------------------
132 : 23 67 34 26 23 23 23 23 23 23
보다시피 빈도수를 단순히 더한다고 해서 맞지 않는다.
이는 특히 숫자 1 의 경우는 32 번 더 반복되는 이유이다.
굳이 설명 안해도 여기까지 이해한 사람들은 왜 32가 더해져야 하는지 알 수 있으리라 생각한다.
결국 1의 빈도수 $ = (21 + 13 + 1 + 32) = 67$ 이 성립한다.
다른 빈도수도 살펴보자.
0 의 빈도수는 $11 + 3 \neq 23$ 으로 맞지 않는다.
이는 30을 계산할 때 1,2,3 ... 30 이 아니라,
01,02,03 ... 30 으로 빈도수를 세어 보면 해결된다.
즉 30은 본래의 빈도수에 더해서 01 ~ 09 까지 0이 9번 더 추가된다.
즉 $ 11 + 3 + 9 = 23$ 이 성립한다.
3의 빈도수 역시 맞지 않다.
$ 20 + 4 \neq 26 $ 인데, 이는
일의 자리수인 +2 만큼 배제된 것이다.
4-2. 예제 - 7,259
마지막으로 난이도를 올려 7,259 라는 숫자를 살펴보자.
7000 : 1992 3100 3100 3100 3100 3100 3100 2101 2100 2100
200 : 31 140 41 40 40 40 40 40 40 40
50 : 5 15 15 15 15 6 5 5 5 5
9 : 0 1 1 1 1 1 1 1 1 1
-----------------------------------------------------------------------------------
2028 3256 3157 3156 3156 3147 3146 2147 2146 2146
7259 : 2145 3256 3216 3156 3156 3156 3146 2406 2146 2146
X O X O O X O X O O
숫자 0, 2, 5, 7 이 일치하지 않는다.
이쯤되면 일종의 패턴을 찾아낼 수 있다.
먼저 7의 빈도수가 왜 다른지 알아보자.
7,259 에서의 7 의 빈도인 : 2,406
7,000 에서의 7 의 빈도인 : 2,101
200 에서의 7의 빈도인 : 40
50에서의 7의 빈도인 : 6
9에서의 7의 빈도인 : 1
모두 더하면 2,147 이 나오는데, 이는 2,406과 정확히
259 만큼 차이난다.
즉 앞전에 등장한 $F$ 의 빈도수를 현재 자기 자신만큼 추가해야 한다는 의미이다.
이를 기반으로 보면 '5' 의 빈도는 9 만큼 추가해 주면 되고 (3147 + 9 = 3156)
'2' 의 빈도는 59 만큼 추가해 주면 된다. (3157 + 59 = 3216)
이제 마지막으로 '0' 의 빈도수만 남았다. 이놈이 다른것에 비해 좀 더 복잡한데,
간단히 말하면 위 132 예제에서 언급한것과 같이 더 낮은 단위의 수를 계산할때
1, 2, 3, 4, 5, ... 가 아니라 01, 02, 03 로 세면 된다.
여기서 핵심은 20 30 등 올바르게 표기된 0 은 위의 공식으로 처리하고,
0020, 02, 0002 등 만을 센다.
200의 경우 더 높은 7000이 존재하니
099 까지만 0의 개수를 세면 된다.
여기서 이또한 규칙이 존재하는데
$$ \large \sum\limits_{i=1}^{B-1} 10^{i} - (B-1) $$
공식을 적용하면 된다.
즉 위 식에서 우리가 구하고자 하는것은 200 에 해당하므로,
108 값이 도출된다.
$2028 + 108 = 2136$
추가로 50에 대해서도 이를 수행해야 한다.
$2137 + 9 = 2145$
5. 코드
#include <iostream>
#include <vector>
#include <math.h>
#include <string>
// 보정되지 않은 각 숫자별 빈도수를 추출하는 클래스.
class NumberFrequency
{
public:
std::vector<std::vector<int>> GetFrequency(const std::vector<int>& numbers)
{
std::vector<std::vector<int>> frequencies;
for (int i = numbers.size(); i > 0; --i)
{
std::vector<int> frequency(10);
auto t_zero = GetZero(numbers[i - 1], i);
auto t_above = GetAbove(numbers[i - 1], i);
auto t_under = GetUnder(numbers[i - 1], i);
// number[i-1]보다 큰 인덱스에 t_above를 더하기
for (int j = numbers[i - 1] + 1; j <= 9; j++) {
frequency[j] = t_above;
}
// 같은 인덱스에 t_above + 1 만큼 더하기
frequency[numbers[i - 1]] = t_above + 1;
// number[i-1]보다 작은 인덱스에 t_under를 더하기
for (int j = 1; j < numbers[i - 1]; j++) {
frequency[j] = t_under;
}
// frequency[0] 에 t_zero 만큼 더하기
frequency[0] = t_zero;
frequencies.push_back(frequency);
}
return frequencies;
}
private:
// F 그 자체는 GetAboveF() + 1
long long GetAbove(int F, int B)
{
if (B <= 1)
{
return 0;
}
return (F * round(pow(10, B - 1))) / 10 * (B - 1);
}
// except for zero
long long GetUnder(int F, int B)
{
if (B <= 1)
{
return 1;
}
return (F + 10) * round(pow(10, B - 2)) + F * round(pow(10, B - 2)) * (B - 2);
}
long long GetZero(int F, int B)
{
if (F == 0)
{
return 0;
}
return (B - 2) * round(pow(10, B - 2)) + (B - 2) -
(round(pow(10, B - 2)) - 1) / 9 + 1 +
(F - 1) * (B - 1) * round(pow(10, B - 2));
}
};
// 각 숫자별 빈도수를 보정하기 위한 클래스.
class NumberCorrect
{
public:
std::vector<int> GetCorrectFrequency(const std::vector<int>& numbers, const std::vector<std::vector<int>>& frequencies)
{
std::vector<int> correctFrequency(10);
int correctFrequency_zero = 0;
auto correctFrequency_other = GetCorrect(numbers, frequencies);
for (int i = 0; i < frequencies.size(); ++i)
{
for (int j = 0; j < 10; ++j)
{
correctFrequency[j] += frequencies[i][j];
}
}
for (int i = 0; i < 10; ++i)
{
correctFrequency[i] += correctFrequency_other[i];
}
for (int i = numbers.size() - 2; i > 0; --i)
{
correctFrequency_zero += GetCorrectZero(numbers[i], i+1);
}
correctFrequency[0] += correctFrequency_zero;
return correctFrequency;
}
public:
std::vector<int> GetCorrect(const std::vector<int>& numbers, const std::vector<std::vector<int>>& frequencies)
{
std::vector<int> correctFrequency(10);
for(int i = numbers.size()-1; i >= 0; --i)
{
for (int j = i-1; j >= 0; --j)
{
correctFrequency[numbers[i]] += numbers[j] * round(pow(10, j));
}
}
return correctFrequency;
}
// 9
// 108
// 1107
// 11106
// 111105
long long GetCorrectZero(int F, int B)
{
long long result = 0;
if (F == 0)
{
return 0;
}
for (int i = 1; i <= B - 1; ++i)
{
result += pow(10, i);
}
result -= B - 1;
return result;
}
};
int main()
{
int N;
std::vector<int> number;
std::vector<std::vector<int>> frequencies;
NumberFrequency nf;
NumberCorrect nc;
std::cin >> N;
while (N != 0)
{
number.push_back(N % 10);
N /= 10;
}
frequencies = nf.GetFrequency(number);
auto totalFrequency = nc.GetCorrectFrequency(number, frequencies);
printf("%d %d %d %d %d %d %d %d %d %d", totalFrequency[0], totalFrequency[1], totalFrequency[2], totalFrequency[3], totalFrequency[4],
totalFrequency[5], totalFrequency[6], totalFrequency[7], totalFrequency[8], totalFrequency[9]);
}코드 일부분이 더러운데, 추후 시간이 나면 수정하도록 하겠다.
6. 결과
시간은 0ms 에 수렴할정도로 빠른 속도를 보여주어
이전 Counting 방식과는 비교도 할 수 없을정도로 빠른 속도를 보여준다.
메모리를 다른 괴수분들 대비 좀 많이 소모하는데 (2MB 정도)
아마 std::vector 의 영향이 좀 있는듯 하다.
7. 개인적인 의견
위에서 나온 공식들이 '왜' 저렇게 도출되었는지 이해하는것이 이 문제의 핵심이므로,
만약 본인이 이 문제를 근본적으로 이해하고자 한다면, '왜 이양반은 이 공식을 썻지?'
한번 고찰해보길 바란다. 그냥 그대로 가져다 쓰면 아무런 공부도 되지 않는다.
그리고 아마 내 풀이 방법이 오피셜한 방법은 아닐것이다.
굳이 읽어보지는 않았지만 아마 백준 공식 풀이방법은 내 풀이방법과 상이할 것이다.
또한 개인적으로 이런 문제는 백준이여서 끝까지 풀어봤지 기업 코딩테스트 문제에서는 안 냈으면 좋겠다.
연속적으로 시간을 들여 푼게 아닌, 중간중간 놀면서 띄엄띄엄 풀긴 하였지만,
규칙성을 찾고 공식으로 도출하고, 포스팅을 쓰는 작업을 동시에 한 순수 시간만 약 2일정도 걸린듯 하다.
왜 다른분들이 이 문제를 푸는데 포기하고 답지먼저 보는지 알겠더라.
+ 진행한 뻘짓
'Algorithm > BACKJOON' 카테고리의 다른 글
| [C++] 백준 1260번 문제 해설 (0) | 2024.03.27 |
|---|---|
| [C++] 백준 15649 문제 해설 (0) | 2023.09.10 |
| [C++] 백준 2166번 문제 해설 (0) | 2022.06.29 |
| [C++] 백준 1305 번 문제 해설 (0) | 2022.06.03 |
| [C++] 백준 19942 번 문제 풀이 (0) | 2021.08.08 |
