이 문제에서 숫자 n이 주어지고 n보다 작거나 같은 모든 점프 숫자를 출력해야 합니다.
점프 숫자 인접한 자릿수가 1만 다른 숫자입니다. 일부 점프 숫자는 4565, 98, 7입니다. 모든 한 자리 숫자는 점프 숫자로 간주됩니다. 235는 점프 숫자가 아닙니다.
이제 문제를 이해하기 위해 예를 들어보겠습니다.
Input: N = 32 Output: 0 1 2 3 4 5 6 7 8 9 10 12 21 23 32
이 문제를 해결하기 위해 0이 시작 노드인 그래프를 가정하고 도달 가능한 모든 노드로 이동합니다. BFS 를 사용하여 탐색할 수 있습니다. 또는 DFS . 이 그래프는 값이 숫자를 뛰어넘는 조건을 사용하여 생성됩니다.
예시
아래 코드는 우리의 솔루션을 구현합니다 -
#include <bits/stdc++.h>
using namespace std;
void traverse(int N, int num) {
queue<int> q;
q.push(num);
while (!q.empty()) {
num = q.front();
q.pop();
if (num <= N) {
cout << num << " ";
int last_dig = num % 10;
if (last_dig == 0)
q.push((num * 10) + (last_dig + 1));
else if (last_dig == 9)
q.push((num * 10) + (last_dig - 1));
else {
q.push((num * 10) + (last_dig - 1));
q.push((num * 10) + (last_dig + 1));
}
}
}
}
void printJumpingNumber(int N) {
cout<<0<<" ";
for (int i = 1; i <= 9 && i <= N; i++)
traverse(N, i);
}
int main() {
int N = 54;
cout<<"Jumping Numbers less than "<<N<<" are :\n";
printJumpingNumber(N);
return 0;
} 출력
Jumping Numbers less than 54 are − 0 1 10 12 2 21 23 3 32 34 4 43 45 5 54 6 7 8 9