Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 스테핑 숫자(Stepping Number) 문제: DFS 재귀로 범위 내 모든 수 찾기

문제 설명

두 정수 low와 high가 주어졌을 때, [low, high] 범위(양 끝값 포함)에 속한 모든 스테핑 숫자(Stepping Number)를 찾아 오름차순으로 정렬된 리스트 형태로 출력해야 합니다.

스테핑 숫자란 인접한 두 자릿수의 절댓값 차이가 정확히 1인 정수를 의미합니다. 예를 들어 321은 3→2, 2→1로 인접 자릿수가 각각 1씩 차이 나므로 스테핑 숫자이지만, 421은 4→2가 2만큼 차이 나므로 해당되지 않습니다.

따라서 low = 0, high = 21이 입력으로 주어지면 결과는 다음과 같습니다.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21]

풀이 접근 방식

이 문제는 DFS(깊이 우선 탐색) 기반의 재귀 호출로 효율적으로 해결할 수 있습니다. 각 숫자의 마지막 자릿수에서 ±1이 되는 값을 이어 붙여가며 새로운 스테핑 숫자를 만들어 내는 방식입니다. 구체적인 단계는 다음과 같습니다.

  • 결과를 임시로 저장할 배열 temp를 준비합니다.
  • solve() 메서드를 작성합니다. 이 메서드는 high, seed, len 세 개의 매개변수를 받으며, len의 초기값은 0입니다.
  • seed가 high보다 크면 더 이상 확장할 필요가 없으므로 즉시 종료(return)합니다.
  • 현재 seed를 temp 배열에 추가합니다.
  • seed가 0이라면 한 자릿수 시작점을 만들기 위해 1부터 9까지의 각 숫자 i에 대해 solve(high, i, 1)을 재귀 호출합니다.
  • 그 외의 경우에는 다음을 수행합니다.
    • lastDigit = seed mod 10으로 마지막 자릿수를 구합니다.
    • lastDigit ≥ 1이고 len + 1 ≤ 10이면 solve(high, (seed × 10) + lastDigit − 1, len + 1)을 호출하여 마지막 자릿수를 1 감소시킨 수를 확장합니다.
    • lastDigit ≤ 8이고 len + 1 ≤ 10이면 solve(high, (seed × 10) + lastDigit + 1, len + 1)을 호출하여 마지막 자릿수를 1 증가시킨 수를 확장합니다.

메인 로직은 다음과 같이 구성됩니다.

  • solve(high, 0, 0)을 호출하여 가능한 모든 스테핑 숫자를 생성합니다.
  • temp 배열을 오름차순으로 정렬합니다.
  • 정답을 담을 배열 ans를 새로 만듭니다.
  • temp의 모든 원소를 순회하면서 low 이상인 값만 ans에 추가합니다.
  • ans를 반환합니다.

자릿수 길이를 최대 10으로 제한하면 오버플로우 없이 안전하게 탐색할 수 있으며, DFS 구조 덕분에 high를 초과하는 가지는 조기에 잘라내기(pruning) 되어 불필요한 연산이 줄어듭니다.

C++ 구현 예제

아래 코드를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
    vector <lli> temp;
    void solve(int high,lli seed=0, int len =0){
        if(seed>high){
            return;
        }
        temp.push_back(seed);
        if(!seed){
            for(int i =1;i<=9;i++){
                solve(high,i,1);
            }
        } else {
            int lastDigit = seed%10;
            if(lastDigit>=1 && len+1<=10)
                solve(high, (seed*10) + lastDigit-1,len+1);
            if(lastDigit<=8 && len+1<=10)
            solve(high, (seed*10) + lastDigit+1,len+1);
        }
    }
    vector<int> countSteppingNumbers(int low, int high) {
        solve(high);
        sort(temp.begin(),temp.end());
        vector <int> ans;
        for(int i =0;i<temp.size();i++){
            if(temp[i]>=low)ans.push_back(temp[i]);
        }
        return ans;
    }
};
main(){
    Solution ob;
    print_vector(ob.countSteppingNumbers(0,40));
}

입력

0
40

출력

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34]

실행 결과를 보면 0부터 40 사이의 모든 스테핑 숫자가 오름차순으로 정렬되어 출력되는 것을 확인할 수 있습니다. 이처럼 DFS 재귀와 가지치기를 활용하면 범위 내 스테핑 숫자를 간결하고 효율적으로 구할 수 있습니다.