1의 개수 세기 - 해답

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

그리고 어제 문제에 O(1)이라고 적었는데 엄밀히 얘기하자면 O(log10 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

Comments

  1. O(log10n)이긴 합니다만, 그 경우 덧셈, 곱셈, 나눗셈의 부하는 세지 않으신게되지 않을까요.

    깊이 생각해보진 않았지만 혹시 다른 방법으로 (예를들어 덧셈만 쓴다던가) 할 수는 없는지 궁금해지네요.

    ReplyDelete
  2. 네, 여기서는 그 정도까진 고려하지 않았습니다. :-)

    위의 코드에서 사용한 int형의 사칙 연산은 어차피 하드웨어에서 할테니 수의 자리수와는 무관한 성능이 나오지 않을까 합니다.

    더 좋은 방법이 있을지는 좀 더 생각해봐야겠네요. 아직까진 위에서 사용한 방법이 최선으로 보입니다.

    ReplyDelete

Post a Comment

Popular Posts