컴퓨팅 사고력을 키우기 위해 아주 가끔 백준이나 코딩도장 같은 알고리즘 문제 풀이하는 웹사이트에 가서 문제 풀이한 것을 구경하곤 합니다.
그때마다 드는 생각 프로그래밍은 정말 머리가 좋은 사람들 아니면 천재들만의 영역이구나!
오늘 코딩 도장에 잠깐 드려서 제목이 "구글 입사 문제 중 하나"라는 문제를 보았습니다. 난이도가 낮은 문제지만 수·알·못이라 그런지 머릿속으로 공식을 그리기가 쉽지 않았습니다.
코딩도장 프로그래밍 문제, 구글 입사 문제 중에서
1부터 10,000까지 8이라는 숫자가 총 몇 번 나오는가?
8이 포함되어 있는 숫자의 갯수를 카운팅 하는 것이 아니라 8이라는 숫자를 모두 카운팅 해야 한다. (※ 예를 들어 8808은 3, 8888은 4로 카운팅 해야 함)
문제 출처 : https://codingdojang.com/scode/393#answer-filter-area
1부터 만까지 8이라는 숫자가 몇 번 들어 가는지 머릿속으로 계산을 해보았습니다.
- 1부터 10까지 8은 1번 들어간다.
- 그리고 나머지 70까지 와 90부터 100까지 1번 들어간다.
- 71부터 80까지는 2번 들어간다.
- 81부터 90까지는 10번 들어간다.
- 100번까지 총 20번 들어간다.
여기까지는 머리로 계산이 됩니다. 그런데 8 백번대를 생각하니 더 이상 머리로 계산이 안됩니다. 제 머리에 한계입니다.
여러분들도 한번 머릿속으로 공식을 그려보시고 아래 답변들을 보시겠습니까?
아래는 풀이한 것 중에 가장 추천 수가 많은 답입니다.
10,000 에는 8 이 없으니 무시하고, 1 부터 9999 까지
X X X 8 인 경우 : 1,000개 ( X X X 는 세자리이므로 0 0 0 ~ 9 9 9 까지 천개)
X X 8 X 인 경우 : 1,000개 ( X X X 는 세자리이므로 0 0 0 ~ 9 9 9 까지 천개)
X 8 X X 인 경우 : 1,000개 ( X X X 는 세자리이므로 0 0 0 ~ 9 9 9 까지 천개)
8 X X X 인 경우 ; 1,000개 ( X X X 는 세자리이므로 0 0 0 ~ 9 9 9 까지 천개)
총 4,000 개 아닌가?
또 다른 분이 풀이한 답입니다.
0000부터 9999라고 생각하고 4자리숫자가 10000개이므로 들어가는 숫자의개수는 4만개 0부터 9까지 10개의 숫자가 같은 비율로 들어가니 4만을 10으로 나누면 4천!
어떤가요?
이 글을 보고 계신 분들 중 저처럼 수알못이라면 어떻게 저런 공식을 만들 수 있지 하면서 감탄하실 것 같아요(저만 그런가요? ㅎㅎㅎ)
코드로는 어떻게 표현해야 구글 입사 시험에서 좋은 점수를 받을 수 있을까요?
정답은 모르겠지만 작성된 코드 중에서 가장 추천이 많은 코드는 파이썬 코드로 아래와 같습니다.
Python :
print(str(list(range(1, 10001))).count('8'))다음으로 추천이 많은 코드는 자바 코드입니다.
Java :
public class CountingEight {
public static void main(String[] args) {
for (int i=0; i<=10000; i++){
searchEight(i);
}
System.out.println("1에서 10,000 사이에 존재하는 8의 개수는? "+count);
}
private static int count = 0;
public static void searchEight(int num){
if (num%10==8) count++;
if (num>10) searchEight(num/10);
}
}파이썬으로 작성된 코드가 많아서 저는 자바스크립트로 풀이 작성을 해 보았습니다.
let arr = Array.from({length: 10000}, (v , i) => i + 1);
let count = arr.join('').match(/8/g).length;
console.log(count); // 4000