[Baekjoon] 1019 책 페이지 - C++

> 문제

https://www.acmicpc.net/problem/1019

1019번: 책 페이지

문제

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

---

> 풀이

문제 자체는 보기엔 간단해 보이지만, 1~n까지의 모든 문자열 각각에 대해 각 자리의 숫자를 카운트 해주면 시간초과가 나는 문제이다. 시간복잡도만 보자면 O(nlogn)인데 문자열 처리에 걸리는 시간에  n <= 10^9 라 시간 초과가 나기 쉽다.

 

Idea 1)

10^k <= n인 최대 k를 구한 뒤,

1~10^k - 1까지 각 숫자마다 나오는 개수를 세고, 다시 10^k~n에서 나오는 숫자를 카운팅 해주는 아이디어이다.

하지만 구현이 복잡했고 더 간단한 방법이 있어 두 번째 방법을 이용했다.

 

Idea 2)

각 자리에서 0~9 각 숫자마다 가질 수 있는 경우의 수를 세주는 알고리즘이다.

이렇게 하면 O(logn)만에 해결 가능하다.

원리는 다음과 같다.

 

ex) n = 54321 일 때

일의자리수 -> 

0은 10, 20, 30, .., 54320까지 5432번 가능하다.

1은 1, 11, 21, .., 54321까지 5432 + 1 = 5433번 가능하다.

2는 2, 12, .., 54312까지 54332번 가능하다.

...

9는 9, 19, .., 54319까지 5432번 가능하다.

 

십의자리수 ->

0은 100~109, 200~209, .., 54200~54209, 54300~54309 까지 총 5432*10 + 10번 가능하다.

1은 10~19, 110~119, 210~219, .., 54210~54219, 54310~54319 까지 총 (5432 + 1) * 10 + 10번 가능하다.

2는 20~29, 120~129, .., 54220~54229, 54320~54321까지 총 (5432+1) * 10 + 2번 가능하다.

...

 

만의자리수 ->

0은 0번 가능하다.

1은 10000~19999까지 10000번 가능하다.

...

4도 40000~49999까지 10000번 가능하다.

5는 50000~54321까지 4321 + 1 = 4322번 가능하다.

 

이 과정에서 규칙들을 찾아보면 각각 i번째 자리일 때 (i는 자릿수 - 1)

> i = 0~ i = length - 2 에서는

- 0 갯수

i번째 자리수가 0보다 클 때)

cnt[0] => (n // 10^i+1) * 10^i

i번째 자릿수가 0일때)

cnt[0] => (n // 10^i+1 - 1) * 10^i + n % 10^i + 1

 

- 1~9 갯수 (각자 j라고 하자)

i번째 자릿수가 그 수보다(j) 클 때)

cnt[j] => (n // 10^(i+1) + 1) * 10^i

i번째 자릿수가 j와 같을 때)

cnt[j] => (n // 10^(i+1)) * 10^i + n % 10^i + 1

i번째 자릿수가 j보다 작을 때)

cnt[j] => (n // 10^(i+1)) * 10^i

 

> i = length - 1 (맨 왼쪽 자리)일때

- 0갯수

cnt[0] = 0

- 나머지 수 갯수(n의 맨 상위 자릿수보단 작은 수 j)

cnt[j] => 10^i

- n의 맨 상위 자릿수

cnt[j] => n % 10^i + 1

 

이렇게 각각 더해 주는 코드를 작성하면 아래와 같다.

// Baekjoon No. 1019 - 책 페이지 220121~220911
// Time Complexity O(logn)
// #Math
/** 
각 자리마다 각 숫자들이 몇 개의 경우의 수를 제공할 수 있는지 케이스를 나누어 각각 세어 답을 구하는 알고리즘
기존의 1~n까지 모든 숫자를 str로 변환해 수를 하나씩 세는 알고리즘은 너무 비효율적임.
*/
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, length;
	int i, j;
	unsigned long long int cnt[10] = { 0 };
	cin >> n;

	// solving
	string number = to_string(n);
	length = number.length();
	// 일의자리~ 맨 상위자리 - 1 까지
	for (i = 0; i < length - 1; i++) {
		// 0은 따로 취급. 0보다 그 자릿수가 작은 경우는 없으므로 그 경우는 제외하고 0일때랑 0이 아닐 때 (클 때)만 고려.
		if(number[length - 1 - i] - '0' != 0)
			cnt[0] += (n / (int)pow(10, i + 1)) * (int)pow(10, i);
		else
			cnt[0] += (n / (int)pow(10, i + 1) - 1) * (int)pow(10, i) + n % (int)pow(10, i) + 1;

		for (j = 1; j < 10; j++) {
			// 그 자리의 숫자 (number[length - 1 - i]) 가 j (현재 가짓수 더하는 수)보다 클 때, 같을 때, 작을 때 세가지로 나누어 분류.
			if (number[length - 1 - i] - '0' > j)
				cnt[j] += (n / (int)pow(10, i + 1) + 1) * (int)pow(10, i);
			else if (number[length - 1 - i] - '0' == j)
				cnt[j] += n / (int)pow(10, i + 1) * (int)pow(10, i) + n % (int)pow(10, i) + 1;
			else
				cnt[j] += (n / (int)pow(10, i + 1)) * (int)pow(10, i);
		}
	}

	i = length - 1;
	// 맨 상위자리
	for (j = 1; j < 10; j++) {
		if (number[0] - '0' > j)
			cnt[j] += (int)pow(10, i);
		if (number[0] - '0' == j) {
			cnt[j] += n % (int)pow(10, i) + 1;
		}
	}
	
	for (i = 0; i < 10; i++)
		cout << cnt[i] << " ";

	return 0;
}

 

> 결론

각 자리마다 나오는 수를 세는 알고리즘이 가장 간결하고, 구현도 그나마 쉬운 편이다.