[백준][1019] 책 페이지

• Problem Link : https://www.acmicpc.net/problem/1019

문제

• N이라는 숫자가 들어올 때 1부터 N까지 각각의 정수가 몇번 나오는지 구해보자

입력

• 첫째 줄이 N이 주어진다.

출력

• 첫째 줄에 0-9가 몇번씩 나오는지 출력한다.

풀이

입력이 1,000,000,000까지 들어온다. 10억이 넘기때문에 O(N)으로 문제를 풀어도 시간 복잡도가 초과된다. 당연히 숫자 하나씩 정수를 세는 방법은 실행 시간 초과 때문에 불가능하다.

입력 값이 굉장히 크기 때문에 이럴 땐 다른 방식으로 접근해야한다. 원래는 자리수 n에 따른 공식을 세워서 일반화하려고 했으나, 0이 맨 앞자리에 있을땐 날라가는 문제 때문에 다른 방식으로 처리를 했다.

그래서 각 자릿수 별로 0-9가 몇번씩 등장하는지 확인하는 것이 더 쉬울 것 같아서 그 방식으로 구현하고자 했다. 따라서 문자열로 숫자를 입력받아서 앞자리를 하나씩 자른다. 방법은 다음과 같다.

ex) 백준 예제입력 5의 N = 543212345를 이용해 설명하겠다.

1. 맨 앞자리 정수를 잘라서 가져온다.
   - 543212345의 맨 앞자리를 자르면 '5'가 들어온다.

   5보다 작은 수들은 1,2,3,4는 5의 자릿수만큼 나왔다는 뜻이고 5는 5의 뒤의 수만큼 나온것을 의미한다. 이 때 반복문은 그냥 0~4까지 실행되도록 하고 마지막에 0을 빼주는 방식으로 진행했다. (맨 앞자리에 0은 올 수 없다.)
   - '1'00000000 ~ '1'99999999 이므로 1은 $10^8$ 나온 것이며 이는 2, 3, 4도 동일하다.
   - 5는 '5'000000000 ~ '5'43212345이므로 5는 '5'를 뺀 뒤 나머지 숫자만큼, 여기서는 43212345번 나온다는 것을 알 수 있다.

2. 따라서 1, 2, 3, 4에 $10^8$씩을 더해준다.
3. 이 때 중요한 점은 1, 2, 3, 4가 진행하면서 뒤의 00000000 ~ 99999999도 추가를 해줘야 하는데 아래 공식을 계산해서 f(8) (현재 8자리이기 때문에)을 0~9자리에 모두 더해준다.

   000 ~ 999 꼴의 수열에서 정수의 개수는 자리수를 k라고 했을때 다음 공식을 만족한다.

   $f(n) = 10^{n-1}*n$

4. 이제 0을 $10^k$만큼 빼주자. 맨 앞자리에 0이 오는 경우는 없기 때문이다.

• 0 00000000 ~ 0 99999999 는 없는 숫자이다. 앞자리 0은 들어오지 않기 때문에 앞자리 0을 $10^k$ 만큼 빼주어야 한다.

5. 이제 맨 앞 숫자를 빼고 남은 숫자만큼 오는 경우를 더해준다.

• 위에서 1~4까지의 처리를 했다면 이제 5가 43212345번 나오는 것을 더해준다.
• 만약 일의 자리 숫자가 진행중이라면 뒤의 남은 숫자가 없으므로 그냥 내 숫자, 이 문제에서는 5가 마지막 숫자이므로 5를 1 늘려준다.

6. 위 1-5번 방법을 했다면 첫번째 자리를 모두 해결했다고 할 수 있다. 이제 맨 앞자리를 제외시키고 다음 자릿수로 내려가서 위 1-5방법을 그대로 진행한다. 아래 코드에 각 번호별로 주석을 달아놨으므로 참고해서 이해해보자.

코드

import sys

input = sys.stdin.readline

n = input().strip()
ans = [0] * 10
k = len(n)

for x in n: #1번이자 5번과정 for문을 자릿수를 내려가면서 진행
    k -= 1  #자리수의 위치
    for i in range(int(x)):
        ans[i] += 10**k							#2번 과정
        for j in range(10):
            if k >= 1:							#k가 1의자리 이상일 때만 하도록 처리
                ans[j] += (10 ** (k - 1)) * k	#3번 과정
    ans[0] -= 10**k								#4번 과정
    if k:
        ans[int(x)] += int("".join(n[-k:])) + 1	#5번 과정
    else:
    	#k=0이면 지금 1의자리 숫자 진행중이므로 뒤의 숫자가 더 없으므로 그냥 내 자리 숫자만 더해준다.
        ans[int(x)] += 1						

print(*ans)