구글 입사시험 "1~10000 사이 8은 몇개?

댓글로 답이 올라와서 찾아봤습니다.

매우 단순하게 해결하면 되는데, 너무 복잡하게 생각했습니다.

이렇게 [멍하게] 풀면 안된다는 사례로 읽어봐주시길.

- 2014.04.21

http://media.daum.net/economic/newsview?newsid=20120621060107706

특히 창의성이나 전문성을 묻는 질문은 까다롭기로 유명하다.
예를 들어 엔지니어에게는 '1부터 10,000까지 8은 모두 몇 개 나오나?'를 묻고는 칠판에 프로그램 코딩을 하듯 알고리즘을 짜서 답변하게 한다.

뉴스와 페이스북에 올라온 글을 보고 쉽게 접근했다가 낭패를 맛봤다.

졸 간단한 문제라고 생각을 했는데, 생각해보니 틀렸다.

이거 너무 쉬운 문제 아닌가하는 생각..
100000+10000+1000+100+10+1=111111 개인데..
1-0 까지 모든 숫자에 적용되는, 1,0만 예외일듯.
저 답이 맞을까.. ㅋㅋ

저렇게 풀면 안 되는 것은 자리수에서 중복으로 나오는 횟수가 셈하게 되기 때문이다.

복잡하게 중복을 수열식으로도 계속해서계산해서 나열하면 안된다.

지난 목요일에 심야 버스를 타고 광주에 갈 일이 있었는데, 심심하던 차에 이거나 풀어보자고 덤볐는데, 의외로 단순한 방법론.

8이 아닌 갯수가 일정한 법칙을 가지고 있다!! 쿠쿵.

10까지 8은 1번 나온다.
  반대로 8이 아닌 개수는 10-1 = 9
100까지는 8은 19번 나온다.
  88에서 두번 계산된다.

  8,18,28... 88,98 80,82.. 88,89 -->10+10-1 따라서 19번
  반대로 8이 아닌 갯수로 계산하면  19 = 100-81 = 10^2 - 9^2 = 100-81=19

확장하면 10^n 까지 8이 아닌 갯수는 9^n개가 나온다.

일반화하면 언제나 10^n - 9^n 답이다.
10000 은 10^4 이므로 10000 - 9^4 = 10000 - 6561 = 3439 개이다.

한가지 추가하자면 1,0 을 제외하고는 모든 숫자는 동일한 답을 가진다.

이 답은 맞을까?

이거 맞춘다고 구글에 입사하는 것은 아닐텐데,

ㅠㅠ

도구를 이용해서 풀자면 0-9까지 4자리가 있는 도장을 순차적으로 돌리면 8은 몇 번 찍히는가 하는 문제와 동일하지 않을까 싶다.