백준 플래5 1019번 Python 풀이

문제 

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

정답

import sys 

# 0부터 9까지 각 숫자의 개수를 저장할 배열
ans = [0] * 10

def calc(n, ten):
    """
    n이라는 숫자 자체에 포함된 각 자리수를 
    ten 만큼 곱해서 ans에 더합니다.
    (예: calc(123, 1) -> ans[1]+=1, ans[2]+=1, ans[3]+=1)
    (예: calc(12, 10) -> ans[1]+=10, ans[2]+=10)
    """
    while n > 0:
        ans[n % 10] += ten
        n = n // 10

def solve(start, end, ten):
    """
    [start, end] 범위 내의 숫자들을 세는 재귀 함수.
    ten은 현재 계산하는 자릿수의 가중치 (1, 10, 100...)
    """
    
    # 1. start를 0으로 끝나는 수로 맞추기
    # ex: start=123 -> 123, 124, ..., 129까지는 따로 계산
    while start % 10 != 0 and start <= end:
        calc(start, ten)
        start += 1
        
    # 만약 start가 end보다 크다면 
    # 이미 계산이 끝났으므로 종료
    if start > end:
        return

    # 2. end를 9로 끝나는 수로 맞추기 
    # ex: end=456 -> 456, 455, ..., 450까지는 개별 계산
    while end % 10 != 9 and start <= end:
        calc(end, ten)
        end -= 1

    # (이 시점에서 start는 0으로, end는 9로 끝남)
    # ex: [130, 449]
    
    # 3. [start, end] 까지의 *1의 자리수*만 계산
    # 예: [130, 449] -> 10의 자리 이상은 [13, 44]
    # 블록의 개수 (cnt) = (44 - 13 + 1) = 32
    cnt = (end // 10 - start // 10 + 1)
    
    # 32개의 블록(130~139, 140~149, ..., 440~449)이 있음
    # 각 블록은 1의 자리에 0~9를 모두 포함
    # 따라서 0~9는 각각 (cnt * ten) 만큼 등장
    for i in range(10):
        ans[i] += cnt * ten

    # 4. 다음 자릿수 재귀 호출 
    # 1의 자리는 모두 계산했으니,
    # [130, 449] -> [13, 44] 범위와
    # 가중치 10을 넘겨서 재귀 호출
    solve(start // 10, end // 10, ten * 10)

n = int(input())
solve(1, n, 1) # 1부터 N까지
print(' '.join(map(str, ans)))

 

풀이

 

N이 최대 10억이기 때문에, 모든 수를 순회하며 각 자리 숫자의 개수를 세는 방법은 불가능하다. 

 

숫자를 나열하다보면 규칙이 보이는데, 0~9까지의 묶음으로 묶어서 세는 것이 가능하다는 것이다. 

예를 들어, 10~39까지의 수를 센다고 해보자. 

10~19까지 일의 자리 수에서 0부터 9까지는 각각 1번씩 등장한다. 

20~29, 30~39까지도 마찬가지이다. 

따라서 일의 자리수를 먼저 센다면, 0부터 9까지에 각각 3을 더해준다고 볼 수 있다. 

그 다음 십의 자리수를 센다면, 10~19에서는 1이 10번, 20~29에서는 2가 10번.. 이 나온다고 볼 수 있다. 

 

이 규칙을 찾아내는 것은 어렵지 않지만, 코드로 구현하는 것에서 애를 많이 먹었다. 

아직 구현 문제에 익숙하지 않다면, 너무 오랜 시간 혼자만의 방법으로 구현하지 말고, 풀이를 보고 이해해 보고, 나중에 시간이 지난 후 다시 풀어 이해도를 점검해보도록 하자. 

 

먼저 나는 재귀를 이용해서 풀어야겠다고 생각했다. 반복되는 규칙이 보였기 때문이다. 

그 규칙은, 0~9까지의 범위로 쪼개면, *10^(N) 단위로 묶어서 셀 수 있다는 것이었다. 

 

이를 위해 정답 함수를 크게 다음과 같은 구조로 만들었다. 

 

Pseudo 코드

solve(start, end, ten):

1. start 의 일의 자리 수가 0이 될 때까지 start를 1 증가시킨다. 그리고 이 과정을 거치게 되는 수는, 각각의 숫자가 몇 번 등장하는지 직접 세어준다. 
2. end 의 일의 자리 수가 9가 될 때까지 end를 1 감소시킨다. 그리고 이 과정을 거치게 되는 수는, 각각의 숫자가 몇 번 등장하는지 직접 세어준다. 
3. 0으로 끝나는 start 와 9로 끝나는 end 사이의 1의 자리 수가 몇 번 등장하는지 세어준다. 
4. 다음 재귀 함수인 solve(start // 10, end // 10, ten * 10) 을 호출한다. 

 

이해하기 어려운 것이 정상이다. 직접 예를 들어보면 이해가 수월할 것이니 이해가 어렵다면 예를 들어보기를 추천한다. 

 

예를 들어, solve(1, ABCD, 1) 을 처음에 호출했다고 하자. 

 

1번에 따라, 1을 10으로 올려준다. 그리고 그 과정을 거치는 1부터 9까지의 수는 ten 만큼 더해준다. 즉 

ans[1] += 1, ans[2] += 1 ... ans[9] += 1 이 된다. 

 

2번에 따라, ABCD 에서 D가 9가 될 때까지, ABCD 에서 1씩 줄여준다. 그리고 그 과정을 거치는 수도 ten 만큼 더해준다. 

ans[ABCD] += 1, ans[ABCD - 1] += 1 ... ans[ABC0] += 1

 

1,2 번이 끝나고 나서 바뀌게 된 start 와 end 를 각각 new_start, new_end 라고 하겠다. 

new_start = 10 

new_end = ABE9 가 되어 있을 것이다. 

 

앞으로의 재귀호출 함수에서 신경쓸 것은 [new_start,new_end] 에 있는 숫자를 세는 것이다. 앞서 버린(?) 숫자들(1~9, ABE9~ABCD)은 이미 그 개수를 다 세었음에 유의해야 한다. 

 

3번의 핵심 포인트는, 한 번의 재귀 호출 함수에서 일의 자리 수"만" 센다는 것이다. 

즉 [10, ABE9] 까지의 수에서 우리가 셀 것은, 일의 자리에 있는 0~9까지의 수에 한정된다. 

십의 자리수, 백의 자리수, 천의 자리수는 다음의 재귀호출에서 센다. 

 

이 관점에서 보면, 일의 자리수를 0~9 까지의 묶음으로 묶어볼 수 있다. 

10~19

20~29

...

ABE0~ABE9 

 

그럼 이때 1의 자리 개수는? 

10~ 단위에서 1개씩,

20~ 단위에서 1개씩, 

...

ABE~ 단위에서 1개씩 나오므로,

각각 ABE-1+1 이 된다. 

ex) ans[0] += ABE-1+1 , ans[1] += ABE-1+1, ... ans[9] += ABE-1+1 

즉 (new_end // 10) - (new_start//10) + 1 로 표현된다. 

 

자, 그럼 지금까지 우리가 센 숫자는 무엇인가?

1 부터 new_start -1까지의 숫자의 모든 자리수,

new_end +1 부터 ABCD 까지의 숫자의 모든 자리수,

그리고 [new_start, new_end] 범위의 일의 자리 수를 모두 세어주었다. 

 

그럼 앞으로 세어야 할 것은 무엇인가?

[new_start, new_end] 범위의 일의 자리 수를 제외한 나머지 모든 자리수를 세어주면 된다. 

 

따라서 4번을 실행할 때, 첫 번째와 두 번째 인자로

solve(new_start // 10, new_end // 10, *) 을 넣는 이유가 이해가 될 것이다. 

 

그럼 ten 에는 어떤 수가 들어가야 할까? 

지금까지 우리가 푼 예제는, 1의 자리 수였기 때문에, 

별도의 ten 을 곱하지 않아도 되었다. 

하지만 십의 자리 수 이상을 셀 때는 이야기가 다르다. 

 

예를 들어, 위 예제에서 solve(1, ABE, 10) 을 호출했다고 가정해보자. 

 

그럼 1번을 수행하기 위해

1 -> 10을 만들 때, 숫자를 1번씩만 더해주면 될까?

잊지 말아야 할 것이, ABE 에서 E는 사실 10의 자리라는 것이다. 

즉 

10

11

12

...

19 

에서의 십의 자리에서의 1의 개수를 세는 것이다. 이때 십의 자리에서 1의 개수는 1개인가? 아니면 10개인가? 

10개이다. 

따라서 

+= 10 을 해줘야 한다. 

 

2번도 마찬가지. 

 

3번은 어떨까? 

마찬가지로 [new_start, new_end] 의 "일의 자리" 를 볼 것이다. new_start 와 new_end 에서는 일의 자리이지만, 사실 우리가 지금 세고자 하는 것은 ABCD에서 십의자리 수에 해당한다. 

 

예를 들어 new_start 가 10, new_end 가 169 이라고 하자. 

[10, 169] 

그럼 일의 자리의 0~9는 각각 몇 번씩 반복될까? 라는 질문에 앞서 했던 것처럼 

169 - 10 + 1 = 160 이라고 대답할 수 있을 것이다. 

10 ~ 19 

20 ~ 29

...

160 ~ 169 

를 보면 그러하니까. 

그런데 사실 우리가 세는 건 진짜 10~169까지의 일의 자리의 수를 세는 것이 아니었다!! 

 

우리가 세는 건 사실, 10X ~ 169X 에서 십의 자리 수를 세는 것이었기 때문에, 

10 에서, 0이 사실 1개가 아니라 10개 였다는 것을 알 수 있다. 

100

101

102

...

109 에서 10의 자리 수의 0은 10개기 때문에!! 

따라서 

(160 - 10 + 1) * 10(==ten) 을 한 값을 ans 의 0부터 9까지의 수에 더해줘야 한다. 

 

백의 자리 수를 셀 땐 그럼 ten 에 몇을 넘겨줘야 할까? 100을 넘겨주면 된다.