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의 수를 셀 수 있다.


by snowall 2012.08.09 11:01
  • goldenbug 2012.08.10 02:51 신고 ADDR EDIT/DEL REPLY

    이 알고리즘을 돌리면 답이 틀릴 것 같습니다. ^^

    • snowall 2012.08.10 11:33 신고 EDIT/DEL

      제 생각에는 맞게 나오는 것 같은데요
      어디가 틀리게 될까요?

  • 꼼지락 2012.08.13 21:09 ADDR EDIT/DEL REPLY

    첫째줄에 1부터 10까지 쓰기 시작하면, 여덟번쨰 컬럼의 일의 자리에 8이 써있고, 1000줄이므로 8이 일단 1000개가 사용됩니다.
    매 10행마다 8번째 행은 8이 십의 자리에 써있고, 그 숫자가 10개가 연속으로 옆으로 써있으므로 1000개의 8이 더 사용됩니다.
    매 100행마다 80번째 행은 8이 백의 자리 수이고 그 행은 10행 지속됩니다. 따라서 1000개의 8이 더 사용됩니다.
    매 1000행마다 800번째 행은 8이 천의 자리수에 사용되고 그 행은 100행 지속됩니다. 따라서 1000개의 8이 더 사용됩니다.
    따라서 총 4000개의 8이 사용됐구요.
    1부터 10^n 까지 사용되는 8의 갯수는 n*10^(n-1) 인것 같군요.
    그리고 snowall님의 알고리즘은 맞구요 ㅎㅎ

    • snowall 2012.08.14 00:50 신고 EDIT/DEL

      그렇군요. 감사합니다.
      그나저나 새 글은 언제 올리시나요 ㅎㅎ