[백준 1019] 책 페이지

1019번: 책 페이지

알고리즘 : 수학

난이도 : 플래티넘Ⅴ

 

1. 문제요약

• 시작 페이지가 1이고, 전체 페이지수 N인 책이 있다. N은 1,000,000,000이하의 자연수로, 입력으로 주어진다.
• 책의 전체 페이지에서  0부터 9까지의 숫자가 각각 몇개씩 등장하는지 구하는 문제이다.
• 예를들어 N = 99일때 구하는 출력은 다음과 같다.
  9 20 20 20 20 20 20 20 20 20

2. 아이디어

• 위 예시에서 알 수 있듯이, 이 문제에서 숫자 0은 페이지의 첫째 자리에 올 수 없기 때문에 특별한 지위에 있다. 이렇게 특별한 취급이 필요한 숫자는 계산을 복잡하게 만들기 때문에, 일단 다른 숫자와 동등하게 취급할 수 있도록 문제를 수정하자. 즉 모든 페이지는 최종 페이지와 똑같은 자릿수를 갖는 숫자로, 0이 채워져 있다고 생각한다. 예를들어 200쪽 자리 책이라면 맨 앞의 1쪽은 001이라고 표시되어 있다고 생각한다는 의미이다.
• 위 가정하에, 9, 99, 999 등 N이 9로만 이루어진 경우에 각 숫자가 등장하는 패턴을 파악해 보자. 간단한 계산을 통해 n개의 9로 이루어진 경우 0부터 9까지 각 숫자는 $n*10^{n-1}$개(이하 key개라고 하자)씩 등장함을 쉽게 알 수 있다. 
• 이제 x99... 9와 같이 첫자리수가 x이고 여기에 n개의 9가 붙어있는 경우 각 숫자가 등장하는 패턴을 파악해 보자. 
  • 000.. 0 ~ 099.. 9 까지는 0은 key + $10^n$개, 나머지 1~9는 key개씩 등장한다.
  • 100.. 0 ~ 199.. 9 까지는 1은 key + $10^n$개, 나머지 0, 2~9는 key개씩 등장한다.
  • 200.. 0 ~ 299.. 9 까지는 2는 key + $10^n$개, 나머지는 0,1, 3~9는 key개씩 등장한다.
  • 즉 첫자리수가 x면  0부터 x까지는 $10^n + key*(n+1)$개, 나머지는 $key*(n+1)$개씩 등장하게 된다.
• 마지막으로, 일반적인 수에 대해 어떻게 계산할지 생각해 본다. 숫자 23456이 주어졌다고 하자.
  • [step 1] 맨 앞자리 숫자는 2이다. 일단 00000에서 19999까지는 위에서 구한 공식에 따라 구할 수 있다.
  • [step 2] 20000부터 23456까지 맨 앞자리 숫자 2는 총 3456 +1 = 3457개 등장한다.
  • 이제 맨 앞자리숫자 2는 제거해도 된다. 즉, 지금까지 구한 개수에 더하여 0000부터 3456까지 각 숫자의 등장 개수를 더해주면 된다.
  • [step 1] 마찬가지로 일단 0000에서 2999까지는 위에서 구한 공식에 따라 구할 수 있고, [step 2] 맨 앞자리 숫자 3은 456 + 1 = 457개 등장한다.
  • 이런식으로 첫자리수를 계속 제거해 나가면 2,3,4,5가 순서대로 제거되어 6만 남게 된다. 마지막 숫자 6에 대하여 0부터 6까지 1씩 더해주면 00000부터 23456까지 모든 숫자의 개수를 구할 수 있다.
• 이제 잠시 미뤄놨던 숫자 0의 처리를 해보자. 0이 총 몇개 더 카운팅 되었는지 파악해야 하는데, 의외로 간단하게 셀 수 있다. 23456에서 생각해보면, 맨 첫쨰자리의 0은 총 10000개 (00000~ 09999), 둘째자리의 0은 총 1000개 (0000~0999), 셋째자리의 0은 총 100개 (000~099), 넷째자리의 0은 총 10개 (00~09), 마지막자리의 0은 총 1개 (0)만큼 더 카운팅 되었음을 알 수 있다. 즉, 주어진 N의 자리수가 n이라면 0은 11...1(n개의 1) 만큼 더 카운팅 된다.

3. 구현과정

• 먼지 00.. 0부터 x99.. 9까지의 모든 숫자를 카운팅하는 함수 counting(x,n)을 정의하자.
  • key = n * 10 ** (n - 1) 이다.
  • 0부터 9까지 i로 순회하면서 check[i]에 key * (x+1)을 더해준다.
  • 0부터 x까지 i로 순회하면서 check[i]에 10 ** n을 더해준다.
• 0부터 9까지의 모든 숫자를 카운팅한 값을 저장할 배열 check = [0 for _ in range(10)]를 생성한다.
• N을 입력받고, N의 길이를 length에 저장한다.
• 0부터 length-1까지 i로 순회하면서, N의 i번째 위치의 숫자를 살핀다.
  • [step 1] counting 함수에 들어갈 인자를 생각해보면, x에는 int(N[i]) -1, n에는 length-i-1이 대입되어야 한다. 다만 숫자가 0인 경우에는 counting함수를 쓸 필요가 없으므로, int(N[i])-1이 -1이 아닌 경우에만 counting 함수를 호출하여 check를 업데이트 한다.
  • [step 2] 숫자 int(N[i])는 int(N[i+1:]) +1 만큼 등장하므로 이 또한 check에 반영시켜 준다.
• for문을 통해 위 두 step을 반복하면 마지막 1의 자리 숫자만 남는다. 이 숫자를 last라 하면, range(last+1)을 i로 순회하면서 check[i]에 1씩 더해주면 된다.
• 마지막으로 특별한 숫자인 0에 대하여 추가로 카운팅된 만큼 빼주어야 한다. 추가로 카운팅된 수는 int('1' * length)로 구할 수 있으므로 이 만큼을 check[0]에서 빼주면 된다.

4. 파이썬 코드

# 00.. 0부터 x99..9(9는 n개)까지의 숫자를 카운팅
def counting(x, n):
    key = n * 10 ** (n - 1)
    for i in range(10):
        check[i] += key * (x + 1)
    for i in range(x + 1):
        check[i] += 10 ** n

check = [0 for _ in range(10)]
N = input()
length = len(N)

for i in range(length - 1):
    a, b = int(N[i]) - 1, length - i - 1
    if a != -1:
        counting(a, b)
    check[int(N[i])] += int(N[i + 1:]) + 1
last = int(N[length - 1])
for i in range(last + 1):
    check[i] += 1
check[0] -= int('1' * length)
print(*check)