구글 입사문제 중에서

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

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

2014/02/14 01:03

길가의풀

여러 알고리즘이 존재할테고, 답도 여러가지인데...구글이 원했던, 혹은 가장 점수를 많이 줬던 정답은 뭘지 매우 궁금?궁금? - 예강효빠, 2017/05/24 01:30 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

328개의 풀이가 있습니다. 23 / 33 Page

public class Count8 { public static void main(String[] args) { int cnt = 0;

    for (int i =0; i<=10000; i++){
        String temp = String.valueOf(i);
        for(int j =0; j<temp.length(); j++){
            if(temp.charAt(j) == '8'){
                cnt++;
            }
        }
    }

    System.out.println(cnt);

}

}

2016/12/29 11:45

Kim Joosang

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

코딩 문제라기 보단 수학적 센스를 묻는 게 맞는 것 같네요 그래도 코딩사이트이니 코드도 짰습니다.

#include <iostream>
int main(void)
{
    int sum = 0;
    for(int i = 1; i <= 10000; i++)
    {
        int temp = i;
        while(temp > 0)
        {
            if(temp % 10 == 8)
                sum++;

            temp /= 10;
        }
    }
    std::cout << "Result: " << sum << std::endl;
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
package main

import (
    "fmt"
    "strconv"
    "strings"
)

func main() {
    var cnt int = 0

    for i := 1; i <= 10000; i ++ {
        cnt += strings.Count(strconv.Itoa(i), "8")
    }
    fmt.Println(cnt)
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

N = 10^K라 가정하고, S(K) = 1부터 10^K 까지의 8의 개수라고 가정하면,

S(0) = 0

S(i) = 10 * S(i-1) + 10^(i-1)

로 정리되므로, 다음과 같이 코드 작성하면 됩니다.

int solution(int N) {
    int S = 0, K = 0, currentN = 1; // initial step, if K = 0
    while (currentN < N) {
        K++;
        currentN *= 10;
        S = 10 * S + (int)Math.pow(10, K-1); // S(K) = 10 * S(K - 1) + 10^(K-1), if K >= 1
    }

    return S;
}

Time Complexity : O(K)

단순히 loop돌면 Time Complexity : O(N * K)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

public class cnt8 {

    static int cnt = 0;

    public static int cnt_8(int inputNum){

        if(inputNum%10 == 8) cnt ++;
        if(inputNum > 10) cnt_8(inputNum/10);

        return cnt;
    }

    public static void main(String[] args) {
        for(int i = 1; i<=10000; i++){
            cnt_8(i);
        }
        System.out.println(cnt);

    }
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
sum = 0

for number in range(1,80):
    str_number = str(number)
    str_len = len(str_number)

    for digit in range(0, str_len):
        if str_number[digit] == '8':
            sum += 1

print sum
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Scala

var count = 0
(1 to 10000).foreach(i => {
    var f = i
    while (f > 0) {
        if (f % 10 == 8) {
            count = count + 1
        }
        f = f / 10
    }
})
println(count);
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
int result = 0;

            for (int i = 1; i <= 10000; i++)
            {
                int temp = i;

                while (temp != 0)
                {
                    if(temp % 10 == 8)
                    {
                        result++;
                    }

                    temp /= 10;
                }
            }

            Console.WriteLine($"result : {result}");
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

숫자 구하는 함수는 fn(숫자)라고 할 때 fn(1234) = fn(123) + fn(4) 라는 점을 이용합니다.

캐시에 매번 계산한 숫자를 저장하고 재사용하여 속도 향상을 노립니다. 캐시 히트율을 높이기 위해서 작은 숫자에서 큰 숫자로 계산을 해야합니다.

import java.util.HashMap;
import java.util.Map;

public class CountNumber {

    public int count(int num, int target) {
        return count(0, num, target);
    }

    private int count(int start, int end, int target) {
        Map<Integer, Integer> cache = new HashMap<>();

        int totalCount = 0;

        for (int i = start; i <= end; i++) {
            Integer cacheCount = cache.get(i / 10);

            int count = (cacheCount == null ? 0 : cacheCount) + (i % 10 == target ? 1 : 0);
            cache.put(i, count);

            totalCount += count;
        }

        return totalCount;
    }

}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <stdio.h>
int main()
{
    int i = 0;
    int j = 0;
    int cnt = 0;

    for (i = 1; i < 10000; i++)
    {
        j = i;
        while (j)
        {
            if ((j%10!=0)&&(j%10)%8==0)
            {
                cnt = cnt++;        
            }
            j = j / 10;
        }
    }
    printf("%d",cnt);
}

결과 4000

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 328
기 타 x 60
python x 121
java x 62
ruby x 5
php x 6
cpp x 30
javascript x 11
lisp x 1
scala x 7
cs x 11
clojure x 1
objectivec x 4
perl x 2
go x 3
haskell x 2
r x 1
matlab x 1