[알고리즘] 8의 개수 구하기 (1~10억)

8의 개수 구하기 (1~10억) C++

구글 입사문제

구글 입사 문제 중, 1부터 100000 사이인 N이 주어지고, 1부터 N까지의 수에서 8이 나오는 횟수를 출력하는 문제가 있다.

여기서 88이라는 숫자가 있으면, 88은 8이 두 개 들어가므로, 2로 카운트해야 된다.

N이 최대 10만이기 때문에, 10만의 자리수는 6이므로, 최악의 시간 복잡도로 생각해도 60만이 된다.

따라서 여러 가지 풀이들이 있겠지만, 각 숫자를 순회하면서 각 숫자의 자리수를 하나하나 확인해도 1초 안에 카운트가 가능하다.

10억으로 확장

N이 1부터 최대 10억까지라고 주어진다면 문제를 어떻게 풀어야 할까?

9억까지라고만 해도 9억 * 9억의 자리수이기 때문에 단순하게 완전 탐색을 하면 시간 초과가 된다.

완전 탐색이 아닌 효율적인 방법을 찾아야 한다.

해결 방법

확장된 문제를 푸는 방법은, 각 자리 수마다 나눠서 8이 등장하는 횟수를 구해야 한다.

예를 들어 N이 4자리의 수 라면, 경우를 4가지로 나눈 뒤 횟수를 더해줘야 한다.

이때 한자리 한자리마다 확인할 때, 그 한 자릿수를 세 가지 경우로 나눠야 한다.

 

8 보다 작을 때

8 일 때

8 보다 클 때

 

세 가지 경우로 나눈 뒤, 해당하는 자리수의 왼쪽 수들과 오른쪽 수 들을 확인하고 카운트하는 방식으로 해결한다.

8 보다 작을 때

52723이라는 숫자가 있고, 세 번째 자리에서 8이 몇 번 나올 수 있는지 확인한다고 하자.

52xxx 일 때는, 세 번째 자리수가 7임으로 8이 등장할 수 없다.

008.., 018.., 028.., ... 518..까지 앞의 수를 확인하면 총 0~51까지까지 52의 경우의 수가 나온다.

8뒤의 .. 은 0부터 99까지 총 100가지의 경우의 수가 나온다. 결과적으로 52*100
즉, (앞자리 수) * 10^뒷자리수를 더해야 한다.

8 일 때

앞에서 8보다 작을 때에서 528..까지 카운트가 되므로 8보다 작을 때의 경우의 수에서,

뒤의 ..에서 나올 수 있는 경우의 수인 0~ 뒷자리 수 -> 뒷자리 수 + 1의 경우의 수를 더해야 한다.

즉 (앞자리 수) * 10^뒷자리수 + 뒷자리 수+1을 더해야 한다.

8 보다 클 때

8 보다 클 때는 529.. 임으로 528..로 시작하는 모든 수를 더할 수 있다.

즉 0~52까지인 경우의 수는 52+1이므로 (앞자리 수+1) * 10^뒷자리수를 더해야 된다.

소스코드

#include <iostream>
using namespace std;
long long result;
long long sumResult(int leftNum, int rightNum, int swc, int digit);
int main(void) {
    int N;
    cin >> N;
    int rightNum = 0;
    int leftNum = N;
    int nowdigit = 1;
    while (leftNum) {
        int lastNum = leftNum % 10;
        leftNum /= 10;
        int swc;
        if (lastNum < 8) swc = -1;
        else if (lastNum == 8) swc = 0;
        else swc = 1;
        result += sumResult(leftNum, rightNum, swc, nowdigit);
        rightNum += lastNum * nowdigit;
        nowdigit *= 10;
    }
    cout << result << '\n';
    return 0;
}
long long sumResult(int leftNum, int rightNum, int swc, int digit) {
    if (swc == -1) {
        return leftNum * digit;
    }
    else if (swc == 0) {
        return leftNum * digit + rightNum + 1;
    }
    else {
        return (leftNum + 1) * digit;
    }
}

모든 경우의 수들을 코드로 나타내면 위와 같이 구현할 수 있다.