코딩 테스트. 구글 입사문제

1부터 10,000까지 8이라는 숫자가 총 몇번 나오는가?

8이 포함되어 있는 숫자의 갯수를 카운팅 하는 것이 아니라 8이라는 숫자를 모두 카운팅 해야 한다.
(※ 예를들어 8808은 3, 8888은 4로 카운팅 해야 함)

 

 

뭔가 구글 입사문제 치고는 너무 쉬운 게 아닐까 생각이 드는 문제입니다. 파이써닉하게 한 줄로도 해결이 가능하죠.

 

str1 = ''

for i in range(1,10001):

    str1 = str1 + str(i)

 

print(str1.count('8'))

 

저는 파이써닉을 안 좋아해서 ㅎㅎ 그냥 1부터 10000까지 숫자를 문자로 바꿔서 더하고(str1= '123456789101112...")

count 함수로 '8'의 숫자를 세면 간단하게 4000이라는 정답이 나옵니다.

 

그런데 이게 사실 프로그래밍으로 풀어야 하는 문제였을까요?? 한번 뇌지컬로 풀어봅시다.

 

8의 숫자를 세는 문제이기 때문에 0부터 9999까지로 범위를 바꿔도 8의 숫자는 달라지지 않습니다. (10000에는 8이 없으니까요.)

마찬가지로 0을 0000으로 바꾸고 모든 0부터 999까지 숫자 앞에 0을 채워서 0000부터 9999까지 생각해도 8의 카운트 숫자는 달라지지 않습니다. 그러면 4자리 숫자가 1만개가( 0000~9999까지) 있으니 총 4만개의 숫자가 존재합니다.

그런데 0000부터 순차적으로 증가하였기 때문에 9999까지 4만개의 숫자에는 0~9까지 10개의 숫자가 매우 균일하게 분포하고 있습니다 예를 들어 모두 같은 숫자인 0000,1111,2222....9999 이렇게 있고 

0이 3개인 경우

0001,0002,0003...0009,    0010,0020,0030....0090,   0100,0200,0300....0900, 1000,2000....9000  

1이 3개인 경우

1110,1112,1113...1119,    1101,1121,1131...1191,   1011......, 0111......

이렇게 각각의 경우 개수가 같습니다. 그래서 총 4만개중 어떤 숫자든 그게 1이든 2이든 10분의 1인 4천개씩 들어있습니다.

 

 이 문제에서 제가 하고 싶은 말은 프로그래밍 실력은 요구사항을 정확하게 구현하는 것이 다가 아닙니다. 물론 그건만 해도 굉장한 실력자는 맞습니다. 하지만 알파고가 이세돌을 이기고 세계 최강의 바둑기사(사람이 아니라 바둑기사가 맞나 모르겠네요.)가 된 것은 맨 처음 돌을 둘 때 19*19의 모든 경우의 수를 생각한 것이 아니라 가장자리, 중앙등 별로 유효한 수가 아닌 것들을 제외하고 생각했기 때문에 이길 수 있었습니다. (아직 바둑판의 모든 경우의 수를 계산할 수 있는 컴퓨터는 없죠.) 

 즉 인간의 사고력과 컴퓨터의 노가다 능력이 만나 기존에 없던 프로그램들이 탄생하는 것이죠.