이 글에서는 숫자 1, 2, 3, 4만을 사용해 만든 수열에서 n번째 수가 몇 자릿수인지 구하는 방법을 알아봅니다.
네 개의 숫자로 구성된 수열은 다음과 같습니다.
1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24...
위 수열에서 n번째 수의 자릿수를 찾아야 합니다. 패턴을 잘 관찰해 보면 다음과 같은 규칙을 발견할 수 있습니다.
1자리 수는 총 4개입니다.
2자리 수는 총 16개입니다.
이 패턴은 4의 거듭제곱 형태로 계속 이어집니다.
예시
입력
7
출력
2
수열에서 7번째 수는 13이며, 이 수의 자릿수는 2입니다.
알고리즘
- 숫자 n을 초기화합니다.
- 결괏값을 저장할 변수와 수열에 포함된 수들의 누적 합계를 저장할 변수, 두 개를 초기화합니다.
- 반복 변수를 4의 거듭제곱만큼 증가시키는 루프를 생성합니다.
- 현재 값을 합계 변수에 더합니다.
- 누적 합계가 n보다 크거나 같으면 루프를 종료합니다.
- 다음 그룹의 수들은 이전 그룹보다 자릿수가 하나 더 많으므로 결과에 1을 더합니다.
- 결과를 반환합니다.
구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int getDigitsCount(int n) {
int i, result = 1, sum = 0;
for (i = 4; ; i *= 4) {
sum += i;
if (sum >= n) {
break;
}
result += 1;
}
return result;
}
int main() {
int n = 57;
cout << getDigitsCount(n) << endl;
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
3
n이 57일 때, 수열에서 57번째 수는 3자리 수에 해당하므로 결과는 3이 됩니다. 이처럼 각 자릿수 그룹의 개수가 4의 거듭제곱(4, 16, 64, ...)으로 늘어난다는 점을 활용하면 반복문 한 번으로 효율적으로 자릿수를 계산할 수 있습니다.