[ 백준 ] 1019 책 페이지 ( Python )

BOJ 1019

책 페이지 수 세기

문제 접근 방법

이 문제는 주어진 페이지 수 N까지의 모든 페이지에 나오는 0부터 9까지의 숫자의 개수를 세는 문제입니다. 처음에는 단순히 1부터 N까지 모든 숫자를 문자열로 변환하여 각 자리수를 세면 될 것 같았습니다. 하지만 이 방법은 N이 최대 10억까지 가능하기 때문에 시간 초과가 발생할 것입니다.

따라서 좀 더 효율적인 방법을 생각해야 합니다. 여기서 착안한 아이디어는 자리수에 따른 규칙성을 활용하는 것입니다.

문제 해결 아이디어

1. 일의 자리에서 1부터 9까지는 1번씩 나타나고, 10부터는 1의 자리가 0이 됩니다.
2. 10의 자리에서는 10~99까지 각 숫자가 10번씩 나타납니다.
3. 100의 자리에서는 100~999까지 각 숫자가 100번씩 나타납니다.
4. 이런 식으로 자리수가 늘어날수록 해당 자리수의 숫자는 (자리수 - 1)의 10^(자리수 - 1)만큼 반복됩니다.

이 규칙을 활용하면 O(log N)의 시간 복잡도로 문제를 해결할 수 있습니다.

풀이 과정

1. 0부터 9까지의 숫자 개수를 저장할 리스트 result를 초기화합니다.
2. 현재 자리수를 나타내는 변수 num을 1로 초기화합니다.
3. N이 0보다 클 동안 아래 과정을 반복합니다:
   • one_digit 함수를 호출하여 현재 자리수에서 9까지의 숫자 개수를 더합니다.
   • N이 10보다 작아지면 남은 숫자에 대해 개수를 더하고 반복을 종료합니다.
   • 그렇지 않으면 현재 자리수에서 0부터 9까지의 개수를 (N // 10 + 1) * num만큼 더합니다. 단, 0의 개수는 num만큼 빼줍니다.
   • 자리수를 올리기 위해 num에 10을 곱하고, N을 10으로 나눕니다.
4. 최종적으로 result 리스트를 출력합니다.

one_digit 함수는 현재 자리수에서 9까지의 숫자 개수를 처리하는 역할을 합니다. 예를 들어 N이 543212345이고 현재 자리수가 1일 때, 543212345부터 543212340까지의 일의 자리 숫자 개수를 세고 N을 543212340으로 업데이트합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(log N)입니다. N이 10으로 나누어질 때마다 자리수가 하나씩 줄어들기 때문입니다. 최악의 경우 N이 10억까지 가능하므로 log(10^9) = 9번의 반복만으로 문제를 해결할 수 있습니다.

전체 코드 보기

```python import sys input = sys.stdin.readline n = int(input()) result = [0] * 10 num = 1 def one_digit(number): while number % 10 != 9: for i in str(number): result[int(i)] += num number -= 1 return number while n > 0: n = one_digit(n) if n < 10: for i in range(n + 1): result[i] += num result[0] -= num break for j in range(10): result[j] += (n // 10 + 1) * num result[0] -= num num *= 10 n //= 10 print(*result) ```

이 문제는 자리수에 따른 규칙성을 활용하여 효율적으로 해결할 수 있었습니다. 단순한 브루트 포스 방식으로는 시간 초과가 발생하겠지만, 수학적인 아이디어를 적용하면 logarithmic 시간에 문제를 해결할 수 있다는 점이 인상적이었습니다.