[백준 1019번] 파이썬 - 책 페이지

백준 1019_책 페이지

시간 제한 2초, 메모리 제한 128MB

# 조건

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

입력

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

출력

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

# 접근 방법

• 10억이므로 우선 브루트포스로는 시간초과가 발생하므로 풀 수 없다.
• 따라서 규칙을 찾아야 되는데 시간이 상당히 오래 걸렸다..
• 찾은 규칙 설명
  • 0~9까지는 앞자리가 변경되도 1개씩 나온다.
  • 이걸 이용해서, 전체 숫자에서 일의 자리 숫자가 등장하는 규칙을 찾을 수 있다.
    • 처음에 1~9이므로 + 1을 해주는 것이다.
    • 또한 0은 처음에 나오지 않으므로 0은 -1 해주면 된다.
    • 29인 경우 2+1개 씩, 129 인경우 129//10 + 1이 된다.
    • 여기서 찾을 수 있는 점은, 일의 자리 숫자가 9라는 보장하에 n // 10 +1개씩 나온다는 것이다.
  • 이번엔 십의 자리를 살펴보자.
    • 199를 예로 들어보자.
    • 우선 199까지 일의 자리에 나오는 수는 199//10 + 1 로 구할 수 있다.
    • 10의 자리에 등장하는 수의 경우 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 이다.
      • 일의 자리와 마찬가지로 199//10//10 + 1개씩 나온다
      • 다만 여기서 생각해주어야 하는 것은, 십의 자리는 10 11 12 13 .. 과 같이 1개가 아닌 10개씩 등장하므로 * 10씩 해서 10개씩 더해주어야 한다.
      • 마찬가지로 0으로 시작하는 십의 자리는 없으므로 -1이 아닌 -10을 해주어야 한다.
  • 여기서 전체 규칙을 찾을 수 있었다.
    • 자릿수가 늘어날 때마다 해당 자릿수의 숫자까지는 (자릿수 -1) * 10 씩 늘어난다는 것이다.
    • 따라서, 입력받은 N의 1의 자릿수부터 페이지 수를 추가하는데 자릿수가 커질 때 마다, 추가되는 페이지수를 10씩 곱해주면 된다.
    • 이 때 더해줘야 되는 수를 num이라고 정의해놨다.
• 우선, 매번 수의 일의 자리를 9로 맞춰주는 함수를 만들어 준다.
  • 일의 자리가 9가 될 때까지 -1씩 해주며 각 숫자를 +num 씩 해주면 된다.
  • +num씩 하는 이유는 위에서 설명했듯이
• 이후 n을 10씩 나누면서 자릿수를 증가시킬 건데, 핵심은 최고 자릿수가 아니라면 위에 언급했듯이 (n//10+1) * num만큼 더해줘야 되는 것이다.
  • 또한 0으로 시작하는 수는 없으므로 자릿수가 변경 될 때마다 num씩 빼주면 된다.
• 즉, 1123을 예로 들면
  1. 1119로 맞춰준다.
  2. 1119까지 1의 자리는 111 + 1개가 나온다.
  3. 0으로 시작하는 1의 자리가 없으므로 -num 후 num * 10, n // 10
  4. 이제 111이 되었으므로 109로 만들어 준 후 반복한다.
  5. 현재 일의 자리인 1은 원래 10의 자리이므로 이전과 달리 1개가 아닌 10개씩 카운트 해주어야 한다.
  6. 이걸 위해서 10씩 * 하며 num을 카운팅 해준 것이다.

n = int(input())  
result = [0] * 10  

# 자릿수마다 카운팅 늘려줄 numnum = 1  

# 일의 자리 9로 맞춰줄 함수  
def one_digit(number):  
    while number % 10 != 9:  
        for i in str(number):  
            result[int(i)] += num  
        number -= 1  

    return number  


# 일의 자리부터 num만큼 더해주며 연산  
# n을 10씩 나눠가며 자릿수 증가시키기  
while n > 0:  
    # 현재 n의 1의 자리 9로 맞추기  
    n = one_digit(n)  

    if n < 10:  
        # 한 자리가 된다면 -> 최고 자리수라면 n까지 num만큼 + 해주기  
        for i in range(n+1):  
            result[i] += num  
    else:  
        # 아직 최고 자릿수가 아니라면 0~9까지   
        for j in range(10):  
            result[j] += (n//10 + 1) * num  

    result[0] -= num  
    num *= 10  
    n //= 10  



print(*result)