8은 몇개인가

http://news.zum.com/articles/2829610

구글 입사 문제중에 1에서 10000까지 8이 몇개 나오는지 세보라는 문제가 있다고 한다.

나의 해법.

a=0
for i in range(10000):
    n=i+1
    while(n>0):
        a+=int(((n+2)%10)==0)
        n/=10
print(a)

몇자 더 줄인 버전.

a=0

i=10000

while(i>0):
    while(n>0):
        a+=int((n%10)==8)
        n/=10

    i-=1
print(a)

증명.

1. (n%10)은 n을 10으로 나눈 나머지이다.

2. (n%10)이 8인 경우 (n%10)==8은 True이다.

3. (n%10)이 8이 아닌 경우 (n%10)==8은 False이다.

4. Python에서 int(True)는 1이다.

5. Python에서 int(False)는 0이다.

6. a+=x는 a에 a+x를 대응시킨다.

7. 1~6에 의해, a+=int((n%10)==8)이 실행되면, n의 1의 자리에 있는 수가 8이면 a는 1만큼 커지고, 8이 아니면 변하지 않는다.

8. n/=10은 n에 n을10으로 나눈 몫을 대응시킨다. 이때, n과 10이 모두 int형이면 나머지는 버려진다.

9. while(n>0)은 n이 0보다 커야 수행되고 0이거나 0보다 작으면 수행되지 않는다.

10. 가장 마지막으로 수행되는 경우는 n이 한자리 수이고, 이후에 n/=10을 수행하면 n=0이 되어 있다.

11. 따라서 while(n>0)구문이 수행되고 나면 a는 n에 있는 8의 수만큼 증가한다.

12. 따라서 while(i>0)구문이 수행되면 1부터 10000사이에 있는 각 정수들이 가지고 있는 8의 수를 셀 수 있다.