구글 입사문제 중에서

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

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

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

298개의 풀이가 있습니다. 23 / 30 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);

}

}

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

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

#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 298
기 타 x 57
python x 105
java x 54
ruby x 5
php x 6
cpp x 27
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