스테핑 넘버(Stepping Number)란 인접한 두 자릿수의 차이가 정확히 1인 숫자를 말합니다. 예를 들어 123, 321, 121 같은 숫자가 여기에 해당합니다. 자릿수 n이 주어졌을 때, n자리 스테핑 넘버가 총 몇 개 있는지 구하는 문제를 C++로 해결해 보겠습니다.
문제 예시
입력
2
출력
17
2자리 숫자 중 가장 작은 수는 10, 가장 큰 수는 99입니다. 이 범위 안에는 12, 23, 34, 45, 56, 67, 78, 89, 98 등 총 17개의 스테핑 넘버가 존재합니다.
알고리즘
- 자릿수 n을 초기화합니다.
- 개수를 저장할 변수 count를 0으로 초기화합니다.
- n자리 숫자의 최솟값은 pow(10, n - 1)로 구합니다.
- n자리 숫자의 최댓값은 pow(10, n) - 1로 구합니다.
- 최솟값부터 최댓값까지 반복하는 루프를 작성합니다.
- 현재 숫자가 스테핑 넘버인지 검사합니다.
- 숫자 내에서 인접한 자릿수 쌍의 차이를 하나씩 확인합니다.
- 차이가 1이 아닌 경우가 하나라도 있으면 false를, 모두 통과하면 true를 반환합니다.
- 현재 숫자가 스테핑 넘버라면 count를 1 증가시킵니다.
- 최종적으로 count를 반환합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
bool isSteppingNumber(int n) {
int previousDigit = -1;
while (n) {
int currentDigit = n % 10;
if (previousDigit != -1 && abs(previousDigit - currentDigit) != 1) {
return false;
}
previousDigit = currentDigit;
n /= 10;
}
return true;
}
int getSteppingNumbersCount(int n) {
int lowestNumber = pow(10, n - 1), highestNumber = pow(10, n) - 1;
int count = 0;
for (int i = lowestNumber; i <= highestNumber; i++) {
if (isSteppingNumber(i)) {
count += 1;
}
}
return count;
}
int main() {
int n = 3;
cout << getSteppingNumbersCount(n) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
32
3자리 숫자 범위(100~999)에는 총 32개의 스테핑 넘버가 존재한다는 의미입니다. 이 방식은 단순하지만 직관적이며, 각 숫자의 자릿수를 하나씩 검사하므로 이해하기 쉬운 장점이 있습니다.