1의 개수 세기 - 해답

벌써 어제 말한 내일이 되었는데 답을 주신 분이 아무도 없어서 좀 뻘쭘하네요. :-P

그리고 어제 문제에 O(1)이라고 적었는데 엄밀히 얘기하자면 O(log₁₀ n)이라고 적었어야 했네요. 죄송합니다.

...

문제를 잠시 생각해보면 1~n까지의 수들 중 1의 개수를 얻기 위해서는 해당 숫자 n의 각 자리의 1의 개수가 모두 몇개나 될지를 구해서 더하면 된다는 사실을 알 수 있습니다.

예를 들어 13이라는 수를 생각해 보면 1~13까지의 수에서 1의 자리에는 1이 모두 몇개나 되는지와 10의 자리에는 모두 몇개나 되는지를 구해 이 값을 더하면 됩니다. 먼저 1의 자리를 생각해 보면 1, 11의 두 개가 있으며 10의 자리의 경우, 10, 11, 12, 13의 네 개가 있습니다. 따라서 2+4=6이라는 값을 구할 수 있습니다.

이번엔 234라는 수에서 10의 자리를 예로 들어 살펴 보겠습니다. 1~234라는 수들 중 10의 자리에 1이 들어가는 수는 10, 11, ..., 19, 110, 111, ... 119, 210, 211, ..., 219들로 모두 30개가 있음을 알 수 있습니다. 이 규칙들을 보면 해당 자리수의 1의 개수를 구하는 공식을 만들 수 있습니다.

234의 10의 자리에 해당하는 1의 개수는 ((234/100)+1)*10이 됩니다. 여기서 +1은 해당 자리수의 수가 0이 아닌 경우에만 더해집니다. 예를 들어 204라면 ((204/100)+0)*10으로 30개가 아닌 20개가 됩니다.

이런 방식으로 234의 각 자리수의 1의 개수를 구하면 1의 자리에 해당하는 1의 개수는 ((234/10)+1)*1=24개가 되고 100의 자리에 해당하는 개수는 ((234/1000)+1)*100=100이 됩니다. 이들 세 수를 모두 합하면 24+30+100=154개가 됩니다.

한가지 추가로 생각해야 할 점은 제일 큰 자리의 수가 1인 경우 위의 공식이 아닌 다른 공식이 필요하다는 점입니다. 예를 들어 123에서 100의 자리에 해당하는 1의 개수는 ((123/1000)+1)*100=100이 아니라 (123-100)+1=24가 됩니다.

설명이 복잡했지만 코드를 보면 간단합니다.

typedef long long int64;

int count1(int64 orig_n)
{
  if (orig_n == 0) return 0;

  int64 n = orig_n;

  int64 cnt = 0;
  int64 times = 1;

  while (n >= 10) {
    int r = n % 10;
    n /= 10;
    cnt += (n + (r != 0)) * times;
    times *= 10;
  }

  if (n > 1)
    cnt += times;
  else
    cnt += orig_n - times + 1;

  return cnt;
}

참고로 1의 개수에는 다음과 같은 규칙도 있습니다. 정수의 세계란 참으로 오묘합니다. :-)

$ ./a.out 9
1
$ ./a.out 99
20
$ ./a.out 999
300
$ ./a.out 9999
4000
$ ./a.out 99999
50000
$ ./a.out 999999
600000
$ ./a.out 9999999
7000000
$ ./a.out 99999999
80000000
$ ./a.out 999999999
900000000