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

C++로 구현하는 연속한 자릿수의 차이가 K인 N자리 숫자 찾기

문제 소개

길이가 N인 모든 음이 아닌 정수 중에서, 인접한 두 자릿수의 절댓값 차이가 항상 K가 되는 숫자들을 모두 찾는 문제입니다. 단, 답에 포함되는 숫자는 앞자리가 0으로 시작하면 안 되며, 숫자 0 자체만이 유일한 예외입니다. 결과는 어떤 순서로 반환해도 무방합니다.

예를 들어 N = 3, K = 7이라면 출력은 [181, 292, 707, 818, 929]가 됩니다. 여기서 070은 유효하지 않은데, 그 이유는 맨 앞에 불필요한 0(선행 영)이 붙어 있기 때문입니다.

접근 방법: 동적 계획법(DP)

이 문제는 자릿수를 하나씩 확장해 가는 동적 계획법(DP)으로 깔끔하게 해결할 수 있습니다. 알고리즘의 전체 흐름은 다음과 같습니다.

  • 크기가 N + 1인 벡터 배열 dp를 생성하고, dp[1]에는 1부터 9까지의 한 자리 숫자를 채워 넣습니다.
  • i를 1부터 N − 1까지 반복합니다.
    • 중복을 방지하기 위한 집합(set) visited를 정의합니다.
    • j를 0부터 dp[i]의 크기 − 1까지 반복합니다.
      • x := dp[i][j]로 현재 숫자를 가져옵니다.
      • lastNum := x의 마지막 자릿수
      • digit := lastNum + K로 계산한 뒤, digit이 0 이상 9 이하이고 (x * 10 + digit)가 아직 방문되지 않았다면 dp[i + 1]에 삽입하고 visited에도 기록합니다.
      • 같은 방식으로 digit := lastNum − K에 대해서도 검사 후 조건을 만족하면 dp[i + 1]에 추가합니다.
  • N이 1이라면 dp[N]에 0을 추가합니다.
  • 최종적으로 dp[N]을 반환합니다.

핵심 아이디어는 기존 숫자의 마지막 자릿수에 K를 더하거나 빼서 새로운 자릿수를 만들고, 그 값이 유효한 범위(0~9) 안에 있을 때만 숫자를 확장하는 것입니다. visited 집합을 활용하면 같은 숫자가 중복해서 저장되는 것을 막을 수 있습니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> numsSameConsecDiff(int N, int K) {
        vector <int> dp[N + 1];
        for(int i = 1; i <= 9; i++){
            dp[1].push_back(i);
        }
        for(int i = 1; i < N; i++){
            set <int> visited;
            for(int j = 0; j < dp[i].size(); j++){
                int x = dp[i][j];
                int lastNum = x % 10;
                int digit = lastNum + K;
                if(digit >= 0 && digit <= 9 && !visited.count(x * 10 + digit)){
                    dp[i + 1].push_back(x * 10 + digit);
                    visited.insert(x * 10 + digit);
                }
                digit = lastNum - K;
                if(digit >= 0 && digit <= 9 && !visited.count(x * 10 + digit)){
                    dp[i + 1].push_back(x * 10 + digit);
                    visited.insert(x * 10 + digit);
                }
            }
        }
        if(N == 1){
            dp[N].push_back(0);
        }
        return dp[N];
    }
};
main(){
    Solution ob;
    print_vector(ob.numsSameConsecDiff(3,7));
}

입력

3
7

출력

[181,292,707,818,929]

정리

이 알고리즘은 각 자릿수마다 최대 두 개의 후보(+K, −K)만 생성하므로, 시간 복잡도는 대략 O(N × 2N) 수준이며 실제로는 매우 효율적으로 동작합니다. 특히 K = 0일 때 중복 제거를 위해 visited 집합을 사용하는 부분이 결과의 정확성을 보장하는 핵심 포인트입니다.