[Beakjoon Online Judge] 1019 - 책 페이지

I 문제 소개

---

문제

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

 

입력

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

 

출력

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

---

II 문제 풀이

---

얼핏봐서는 정말 간단해보이는 문제였다.

문제만 따라간다면 그냥 N까지 for문 돌리면 끝나겠네 싶었다.

그렇게 1달전에 무참히 패배했다.

코드 길이를 보면 알 수 있듯, 코드를 전혀 다르게 세 번 짰었다.

for문을 N까지 돌리면서, 그 숫자의 자리수를 계산해 하나씩 더해주는 과정 O(n^2)으로는 풀 수 없다는 결론에 도달했다.

따라서 재정비가 필요했다.

 

패드가 없어 평소에 이렇게 메모장을 이용해 푸는데, 이 문제를 풀 때 패드의 필요성을 정말 뼈저리게 느꼈다.

 

내가 생각한 알고리즘은 이러했다. 0~9이 각각 몇 개인지 세줄 numberArray[10]에

 

1) 1의 자리에서 0~9가 각각 오는 개수 구해서 저장하기
2) 10의 자리에서 0~9가 각각 오는 개수 구해서 저장하기
...
n) 10^(n-1)의 자리에서 0~9가 각각 오는 개수 구해서 저장하기

 

'45678'이라는 수가 주어졌다고 가정해보자. 이걸 1)~n)을 적용한다고 했을 때, 당장 2번에서 10의 자리에서 개수를 구해야하는데, 10의 자리에 7이 오는 경우 마지막에 45670~45678까지 9개가 있는데, 6 이하에서는 10개씩 있고 8이상에서는 6 이하보다 10개씩 적다. 즉, 생각해야하는 부분이 많아 계산이 너무 불편해진다.

 

이를 해결할 아이디어는, "구간을 깔끔하게 자르자"였다.

1의 자리를 셀 때는 45678이 아닌 45670까지 세고,

10의 자리를 셀 때는 45670이 아닌 45600까지 세고,

100의 자리를 셀 때는 45600이 아닌 45000까지 세고,

1000의 자리를 셀 때는 45000이 아닌 40000까지 세는 것이다.

 

이렇게 하면 계산상 앞에서 처럼 자투리를 세는 일 없이 모든 수가 같은 개수만큼 갖는다.

 

그런데 45670까지 셀 때 45670을 포함해서 세야하는가? 라는 의문이 들 수 있는데, 답은 '그렇다'다.

왜냐하면 10의 자리에 6이 있는걸 계산해보자 했을 때 마지막 범위는 45660 ~ 45669이지 45660 ~ 45670이 아니기 때문이다. 그래서 정확히는 범위를 산정할 때. 45670이 아니라 45669을 만들어줘야할 것이다.

 

그러면 자투리를 계산하는 방법만 알면 되겠다.

 

일단 1의 자리를 깔끔하게 계산하기 위해서는 45678을 45670으로 만들어주면 된다.

45678에서 45670을 만들었다고 치고, 100의 자리에 각 수가 오는 개수를 셀 때, 6의 경우 7 8 9보다 70개가 더 많고, 6보다 작은 0에서 5까지는 7 8 9보다 100개가 더 많았다.

해당 자리수에 있는 숫자를 기준으로, 그 수보다 작은 수들은 그 수보다 큰 수들에 비해 (자리수에 해당하는 10의 제곱수)만큼 더 많았고, 그 수는 (해당 자리수 바로 아래 자리수의 수)만큼 더 많은 것이다.

 

* 자리수에 해당하는 10의 제곱수 => 100의 자리를 계산하고 있다면 100을 뜻함

* 해당 자리수 바로 아래 자리수의 수 => 45670에서 100의 자리를 계산하고 있다면 100으로 나눈 나머지인 70을 뜻함

 

그러면 45678을 기준으로 내가 설계한 알고리즘이 돌아가는 과정을 설명해보겠다.

0) 45678이 들어옴
1) 45678 -> 45670으로 만듦 (이건 그냥 for문으로 계산해도 될 것 같음)
2) 45670에서 10의 자리에 오는 수를 계산할거임
  - 10의 자리에 있는 7보다 작은 수인 6까지는 각각 4570개가 있고 7에서는 4567개, 7보다 큰 수들은 4560개가 있음 엥?

엥? 생각해보니 책에서 1쪽은 1쪽이지 00001쪽이 아니다. 따라서 0은 규칙을 무시하고, 따로 만들어줘야했다.

그러고보면 앞에 0이 안붙는 순간은 10, 100, 1000, 10000... 입력받은 숫자의 최대 자리수에 1이 오는 순간부터 0이 붙지 않는다.

그러면 편안한 계산을 위해 거기까지는 미리 계산해줘도 되지 않을까?

그래서 나열해보며 규칙을 생각해보았다.

 

1 ~     9 : 0  1  1  1  1  1  1  1  1  

1 ~    99 : 9 20 20 20 20 20 20 20 20 20

1 ~   999 : 189 300 300 300 300 300 300 300 300 300

1 ~  9999 : 2889 4000 4000 4000 4000 4000 4000 4000 4000 4000

1 ~ 99999 : 38889 50000 50000 50000 50000 50000 50000 50000 50000 50000

1 ~ n개의 9 : (n-2)(n-2개의 8)(9) (n*(10의 n-1승)) (n*(10의 n-1승)) (n*(10의 n-1승)) (n*(10의 n-1승))...(n*(10의 n-1승))

라는 규칙이 보였다. 식으로 만드려고 해서 이렇지 그냥 0에서는 (맨 앞 숫자 +1 / 8 한개 늘리고 / 맨 끝에 9)의 규칙이고 나머지 수에서는 (맨 앞 숫자 +1 / 0 한개 늘리기)이다.

 

그래서 이걸 미리 계산해준다면, 우리는 이제 45678을 10000부터 45678까지만 세주면 된다.

 

0) 45678이 들어옴

1) 45678 -> 45670으로 만듦 (이건 그냥 for문으로 계산해도 될 것 같음)
  1-1) 45670을 포함해서 세줘야함.

2) 45670에서 10의 자리에 오는 수를 계산할거임. 단 10000부터 45670까지!
  2-1) 45600 - 10000 = 35600 (10의 자리에 오는 수를 계산하려면 100의 자리가 몇 번 넘어가는지 알면 된다)
  2-2) 35600 / 10 = 3560 (막상 빼고나니 10으로 나눠줘야할 것 같아서 나눴다.)
  2-3) 10의 자리인 7을 기준으로, 6까지는 45660 ~ 45669 구간이 있으므로 10이 더 많다.
  2-4) 10의 자리인 7에서는 1번에서 이미 수를 45670으로 만들었기 때문에 더 셀 게 없다. 45670에서 7 아래에 있는 0이 더 많다고 표현할 수 있겠다.
  2-5) 45670 -> 45600으로 만듦. (단, 45670은 계속 저장해놔야할듯)

3) 45600에서 100의 자리에 오는 수를 계산할거임. 역시 10000부터 45600까지!
  3-1) 45000 - 10000 = 35000
  3-2) 35000 / 10 = 3500 (쓰다가 알게 된 사실인데, 10은 고정인 것 같다.)
  3-3) 100의 자리인 6을 기준으로, 5까지는 100이 더 많다.
  3-4) 100의 자리인 6에서는 45670에서 6 아래에 있는 70이 더 많다.
  3-5) 45600 -> 45000으로 만듦.

... (1000은 생략)

5) 40000에서 10000의 자리에 오는 수를 계산할거임. 10000부터 40000까지
  5-1) 생각해보면 10000부터 40000까지 10000의 자리에 오는 수를 계산한다면, 1부터 3까지는 모두 10000개씩 있고, 4에서는 5670개가 있을 것이다.
  5-2) 이 부분은 1~9999를 미리 계산해놨기도 하고, 0이 없기도 하고 해서 특수한 경우라 예외로 규칙을 만들어주기로 했다.

 

이렇게 장황하게 설명해도 결국 무슨 말인지 이해하지 못할 것이다. 나도 설명하기 어렵다.

이제부터 코드로 설명해보겠다.

 

0. 초기 환경 설정

---

#include <iostream>
#include <vector>

using namespace std;

void printArray(int numberArray[10])
{
	int i;
	for (i = 0;i < 10;i++)
		cout << numberArray[i] << " ";
}

int tenPow(int n)
{
	int i, num = 1;
	for (i = 0;i < n;i++)
		num *= 10;
	return num;
}

int main(void)
{
	int numberArray[10] = { 0,0,0,0,0,0,0,0,0,0 };
	int N;
	cin >> N;

	int i,j,k;
	int temp;
    
	printArray(numberArray);
	return 0;
}

문제 특성상 자리수를 이용해야해서 tenPow()를 만들었고,

마지막에 numberArray를 출력하기 위해 printArray()함수를 따로 만들었다.

 

main함수에서는 N을 입력받았고, numberArray를 만들었다.

N까지 셀 때 n이라는 숫자가 나타나는 횟수는 numberArray[n]에 저장할 것이다.

 

1. 자리수에 따른 초기값 부여

---

if (N > 999999999)
{
	numberArray[0] = 788888889;
	for (i = 1;i < 10;i++)
		numberArray[i] = 900000000;
	temp = 1000000000;
}
else if (N > 99999999)
{
	numberArray[0] = 68888889;
	for (i = 1;i < 10;i++)
		numberArray[i] = 80000000;
	temp = 100000000;
}
else if (N > 9999999)
{
	numberArray[0] = 5888889;
	for (i = 1;i < 10;i++)
		numberArray[i] = 7000000;
	temp = 10000000;
}
else if (N > 999999)
{
	numberArray[0] = 488889;
	for (i = 1;i < 10;i++)
		numberArray[i] = 600000;
	temp = 1000000;
}
else if (N > 99999)
{
	numberArray[0] = 38889;
	for (i = 1;i < 10;i++)
		numberArray[i] = 50000;
	temp = 100000;
}
else if (N > 9999)
{
	numberArray[0] = 2889;
	for (i = 1;i < 10;i++)
		numberArray[i] = 4000;
	temp = 10000;
}
else if (N > 999)
{
	numberArray[0] = 189;
	for (i = 1;i < 10;i++)
		numberArray[i] = 300;
	temp = 1000;
}
else if (N > 99)
{
	numberArray[0] = 9;
	for (i = 1;i < 10;i++)
		numberArray[i] = 20;
	temp = 100;
}
else if (N > 9)
{
	numberArray[0] = 0;
	for (i = 1;i < 10;i++)
		numberArray[i] = 1;
	temp = 10;
}
else if (N > 0)
{
	temp = 0;
}

솔직히 조금 민망한 코딩이다.

규칙으로 만들 수 있었는데, 풀다가 너무 복잡한 나머지 너무 화가나서 범위도 10억까지밖에 없길래 그냥 하드코딩했다.

계산 시간을 단축했다는 것에 의의를 두었다.

그리고 temp로 이 수의 자리수에 따른 10의 제곱수를 미리 저장해놓았다.

 

1-1. 예외처리

if (temp == 0)
{
	for (i = 1;i <= N;i++)
		numberArray[i]++;
}

생각해보다가 1의 자리의 수가 들어오면 내가 만든 규칙에 딱 들어맞지도 않고 들어맞더라도 오히려 그쪽이 시간이 오래걸리는 방향 같아서 temp를 이용해 미리 예외처리했다.

 

2. 1의 자리를 0으로 만들기

---

for (i = N;i % 10 != 0;i--)
	for (j = 1;j <= i;j *= 10)
		numberArray[(i / j) % 10]++;
for (j = 1;j <= i;j *= 10)
	numberArray[(i / j) % 10]++;

만약 45678이 들어왔다면 45670으로 만드는 과정이다.

단, 앞에서 말했다시피 45670이 아닌 45669까지의 범위를 만들어야하므로 45670까지 세주기 위해 밑에서 한번 더 for문으로 계산했다.

그리고 이 연산 결과로 i에는 45670이 저장된다.

 

3. 자리수별로 계산

---

int mytemp = i;
vector<int> vecNum;
for (j = temp;j >= 1;j /= 10)
{
	vecNum.push_back(mytemp / j);
	mytemp -= j * vecNum.back();
}

일단 왠지 필요할 것 같아서 벡터를 만들어 45670을 각각 끊어서 4,5,6,7,0으로 저장했다.

 

int token = vecNum.back(); // token이라는 변수에 벡터 맨 끝의 값으로 초기화. 0
for (j = 1;j <= vecNum.size();j++)
{
	if (j == 1) // 1의 자리수를 계산
	{
		for (k = 0;k < 10;k++) // (45670-10000)/10을 각각 더해줄 것임
			numberArray[k] += ((i - temp) / 10);
		i -= vecNum[vecNum.size() - j - 1] * tenPow(j); // (45670 -= 7 * 10)
	}
	else if (j != vecNum.size()) // 1의 자리수는 아니면서 가장 큰 자리수도 아님
	{
		for (k = 0;k < 10;k++)
			numberArray[k] += ((i - temp) / 10);
		i -= vecNum[vecNum.size() - j - 1] * tenPow(j); // 여기까지는 위와 같음
        
		for (k = 0;k < vecNum[vecNum.size() - j];k++) // 45600이라면 6보다 작은 수에 100씩 더함
			numberArray[k] += tenPow(j - 1);
		numberArray[vecNum[vecNum.size() - j]] += token;
		token += vecNum[vecNum.size() - j] * tenPow(j - 1); // token은 45600에서 6에 70을 더할 때 씀
	}
	else // 가장 큰 자리수
	{
		for (k = 1;k < vecNum[0];k++)
			numberArray[k] += temp;
		numberArray[k] += token;
	}
}

이게 계산의 전부인데, 어떻게 설명하기 쉽지 않다.

이 반복문은 N의 자리수별로 계산한다.

 

token이라는 변수는 어떻게 보면 앞에서 말했던 "자투리"를 계산하기 위해 필요한 존재다.

45670에서 10의 자리를 계산할 때 자투리 : 0

45670에서 100의 자리를 계산할 때 자투리 : 70

45670에서 1000의 자리를 계산할 때 자투리 : 670

이런 식이기 때문에 그때그때 vecNum과 tenPow()를 이용해 +0, +70, +600 의 형식으로 조정했다.

 

그런데 한 번의 과정에서 만든 token은 그 다음 과정에서 쓰인다.

=> 10의 자리를 계산할 때, 계산을 하고 난 마지막에 token이 70이 되고 이 70이 100의 자리를 계산할 때 쓰인다.

 

따라서 초기 값을 부여해주고 먼저 numberArray에 더해진 다음에 token이 커지는 순서로 만들었다.

이 token은 마지막에 가장 큰 자리수에서도 요긴하게 쓰인다.

 

4. 최종

---

#include <iostream>
#include <vector>

using namespace std;

void printArray(int numberArray[10])
{
	int i;
	for (i = 0;i < 10;i++)
		cout << numberArray[i] << " ";
}

int tenPow(int n)
{
	int i, num = 1;
	for (i = 0;i < n;i++)
		num *= 10;
	return num;
}

int main(void)
{
	int numberArray[10] = { 0,0,0,0,0,0,0,0,0,0 };
	int N;
	cin >> N;

	int i,j,k;
	int temp;
	if (N > 999999999)
	{
		numberArray[0] = 788888889;
		for (i = 1;i < 10;i++)
			numberArray[i] = 900000000;
		temp = 1000000000;
	}
	else if (N > 99999999)
	{
		numberArray[0] = 68888889;
		for (i = 1;i < 10;i++)
			numberArray[i] = 80000000;
		temp = 100000000;
	}
	else if (N > 9999999)
	{
		numberArray[0] = 5888889;
		for (i = 1;i < 10;i++)
			numberArray[i] = 7000000;
		temp = 10000000;
	}
	else if (N > 999999)
	{
		numberArray[0] = 488889;
		for (i = 1;i < 10;i++)
			numberArray[i] = 600000;
		temp = 1000000;
	}
	else if (N > 99999)
	{
		numberArray[0] = 38889;
		for (i = 1;i < 10;i++)
			numberArray[i] = 50000;
		temp = 100000;
	}
	else if (N > 9999)
	{
		numberArray[0] = 2889;
		for (i = 1;i < 10;i++)
			numberArray[i] = 4000;
		temp = 10000;
	}
	else if (N > 999)
	{
		numberArray[0] = 189;
		for (i = 1;i < 10;i++)
			numberArray[i] = 300;
		temp = 1000;
	}
	else if (N > 99)
	{
		numberArray[0] = 9;
		for (i = 1;i < 10;i++)
			numberArray[i] = 20;
		temp = 100;
	}
	else if (N > 9)
	{
		numberArray[0] = 0;
		for (i = 1;i < 10;i++)
			numberArray[i] = 1;
		temp = 10;
	}
	else if (N > 0)
	{
		temp = 0;
	}

	if (temp == 0)
	{
		for (i = 1;i <= N;i++)
			numberArray[i]++;
	}
	else
	{
		for (i = N;i % 10 != 0;i--)
			for (j = 1;j <= i;j *= 10)
				numberArray[(i / j) % 10]++;

		for (j = 1;j <= i;j *= 10)
			numberArray[(i / j) % 10]++;

		int mytemp = i;
		vector<int> vecNum;
		for (j = temp;j >= 1;j /= 10)
		{
			vecNum.push_back(mytemp / j);
			mytemp -= j * vecNum.back();
		}

		int token = vecNum.back();
		for (j = 1;j <= vecNum.size();j++)
		{
			if (j == 1)
			{
				for (k = 0;k < 10;k++)
					numberArray[k] += ((i - temp) / 10);
				i -= vecNum[vecNum.size() - j - 1] * tenPow(j);
			}
			else if (j != vecNum.size())
			{
				for (k = 0;k < 10;k++)
					numberArray[k] += ((i - temp) / 10);
				i -= vecNum[vecNum.size() - j - 1] * tenPow(j);
				for (k = 0;k < vecNum[vecNum.size() - j];k++)
					numberArray[k] += tenPow(j - 1);
				numberArray[vecNum[vecNum.size() - j]] += token;
				token += vecNum[vecNum.size() - j] * tenPow(j - 1);
			}
			else
			{
				for (k = 1;k < vecNum[0];k++)
					numberArray[k] += temp;
				numberArray[k] += token;
			}
		}
	}
	printArray(numberArray);
	return 0;
}

 

III 느낀점

---

이 문제는 solved.ac 기준, 골드 1이라는 높은 난이도를 자랑한다.

정말 어려운 문제였고, 어떤 끄적일 도구 없이 메모장으로 풀기는 나에게 벅찼다.

 

풀고 나서의 성취감은 엄청났지만, 막상 이것을 남에게 설명하려니 너무도 복잡했다.

 

솔직히 말해서 이번에 이 문제를 풀 때에는 처음부터 계획을 세웠던게 아니라, 마치 수열에서 점화식을 구하듯 하나하나 다 해보고 규칙을 찾아서 풀었다.

규칙을 찾을 때는 큰 수는 직접 계산하기 머리도 아프고 정확도도 옛날에 만들어놓은 O(n^2) 짜리 코드를 썼다.

꼼수랑 꼼수는 다 써서 푼 것 같다.

 

그리고 하드코딩도 있었다.

 

어려운걸 풀었다는 기쁨도 잠시 반성할 게 많은 코딩이었다.

복잡한 계산도 아름답게 쓰려는 노력이 필요할 것 같다.

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 1019번 책 페이지 C++

BOJ 1019번 책 페이지 C++

백준 1019번 책 페이지 C++