이 문제에서는 하나의 수 n이 주어지며, n보다 작거나 같은 모든 점핑 넘버를 출력해야 합니다.
점핑 넘버란?
점핑 넘버(Jumping Number)는 인접한 두 자릿수의 차이가 정확히 1인 수를 말합니다. 예를 들어 4565, 98, 7은 모두 점핑 넘버입니다. 한 자리 숫자는 모두 점핑 넘버로 간주되며, 반면 235처럼 인접 자릿수 차이가 1이 아닌 수는 점핑 넘버가 아닙니다.
문제 이해를 위한 예시
입력: N = 32
출력: 0 1 2 3 4 5 6 7 8 9 10 12 21 23 32
접근 방법
이 문제를 해결하려면 그래프 개념을 활용할 수 있습니다. 0을 시작 노드로 설정하고, 도달 가능한 모든 노드를 탐색하는 방식입니다. 탐색에는 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)를 사용할 수 있습니다.
그래프는 '새로운 값이 점핑 넘버가 되도록 하는 조건'에 따라 생성됩니다. 즉, 현재 수의 마지막 자릿수에 ±1을 더한 값을 다음 자릿수로 붙여 나가면 인접 자릿수 차이가 항상 1인 수, 즉 점핑 넘버만 만들어집니다.
- 마지막 자릿수가 0이면 → 다음 후보는 (num × 10) + 1 하나뿐입니다.
- 마지막 자릿수가 9이면 → 다음 후보는 (num × 10) + 8 하나뿐입니다.
- 그 외의 경우 → (num × 10) + (마지막 자릿수 − 1)과 (num × 10) + (마지막 자릿수 + 1) 두 가지 후보를 큐에 추가합니다.
C++ 구현 예제
아래 코드는 위에서 설명한 BFS 기반 해결 방법을 구현한 것입니다.
#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
코드 설명
traverse 함수는 시작 숫자를 큐에 넣고, 큐가 빌 때까지 다음 과정을 반복합니다.
- 큐에서 숫자를 꺼냅니다.
- 그 숫자가 N 이하라면 출력하고, 마지막 자릿수를 기준으로 다음 점핑 넘버 후보들을 계산해 큐에 추가합니다.
printJumpingNumber 함수는 0을 먼저 출력한 뒤, 1부터 9까지 각각의 한 자리 숫자를 시작점으로 하여 traverse를 호출합니다. 이렇게 하면 N 이하의 모든 점핑 넘버를 빠짐없이 찾을 수 있습니다.
BFS를 사용하기 때문에 탐색 순서는 오름차순 정렬과 다르게 나타날 수 있지만, 결과적으로 N 이하의 모든 점핑 넘버가 출력됩니다. 필요하다면 결과를 별도의 컨테이너에 저장한 후 정렬하여 출력할 수도 있습니다.