코딩 문제 질문
글쓴이: rayman / 작성시간: 수, 2014/01/08 - 9:11오후
문제를 요약하면
<입력>
1 이상 1,000,000,000 이하인 정수 N 입력
<출력> 1 ~ N까지의 정수에 포함되어 있는 각 숫자(0 ~ 9)의 갯수를 각각 출력
<예제 입력> 11
<예제 출력> 1 4 1 1 1 1 1 1 1 1
이 문제를 각 수를 이루고 있는 숫자들을 분리해서, 각각의 숫자의 갯수를 세는 방식으로 해결했는데요.
이렇게 하면 N = 1000000000과 같이 큰 수가 입력되었을 경우 시간이 너무 많이 걸리는 문제가 생깁니다.
어떻게 하면 시간을 단축시킬 수 있는 코드를 작성할 수 있을까요?
제가 작성한 코드입니다.
#include <stdio.h>
void count(int n);
int cnt[10] = {0, };
void main()
{
int n, i, j;
scanf("%d", &n);
for(i = 1; i <= n; i++) {
count(i);
}
for(i = 0; i < 10; i++) {
printf("%d ", cnt[i]);
}
puts("");
}
void count(int n) {
while(n != 0) {
cnt[(n % 10)]++;
n = n / 10;
}
}Forums:
자릿수 별로
자릿수 별로 계산하는게 빠르지 않을지,
예를 들어 0에서 99까지는 각 숫자가 20개씩 있으므로, 이를 별도로 계산하지 않고 남는 부분만 계산한다던가.
작업을 10단위로 만드세요.
10단위로
대충 계산해보니..
자릿수별로 공식이 대강 나오는군요.
10일때 - 각자리 1회씩
100일때 - 각자리 20회씩 (10으로 구성된 2차원 공간)
1000일때 - 각자리 30회씩 (3차원 공간)
10000일때 - 각자리 40회씩 (4차원 공간)
....
대충 이런식의 공식이 나오는데, 여기서 고려해야 될것은 0으로 시작하는 숫자는 실제론 0외엔 없으므로 이걸 빼야 한다는 것.
이렇게 각 자릿수에 맞게 뽑아내고 곱하면 얻을 수 있을 걸로 보입니다.
적당히 생각한것이니 맞지 않을 수도 있고 맞는다 해도 보완이 더 필요하겠지만 어쨌든 이런식의 법칙을 알아내는게 해당 과제의 목표라 생각이 됩니다.
프로그래밍보단 수능시험에 어울리는 문제같기도 하고 그러네요.. 입력과 출력이 그냥 공식으로 표현될 걸로 보여서요.
--
For example, count(327, 0) =
For example,
count(327, 0)
= count (320, 0) + count (7, 0)
= 32 times x [0-9] + once x [1-7]
==> In general, count(n, 0) = floor(n / 10) times x [0-9] + count(n % 10, 0) where n >= 10.
==> For n < 10, count(n, 0) is evident.
count(327, 1)
= 10 times x count (31, 0) + 8 times x [2]
= 10 times x (count (30, 0) + count(1, 0)) + 8 times x [2]
= 10 times x (3 times x [0-9] + once x [1]) + 8 times x [2]
count(327, 2)
= 100 times x count (2, 0) + 27 times x [3]
==> In general, count(n, m) = 10^m times x count(floor(n / 10^m) - 1, 0) + (n % 10^m) times x [a concerned digit]
count_total(327) = count(327, 2) + count(327, 1) + count(327, 0)
==> In general, count_total(n) = sum_m { count(n, m) } where n is between 10^m and 10^(m+1).
Now, develop, verify, etc.
문자열로 바꿔서 이어 붙인 다음에 세도 되겠네요.
문자열로 바꿔서 이어 붙인 다음에 세도 되겠네요.
--
마잇
댓글 달기