문제 개요
정수의 각 자릿수가 바로 앞 자릿수보다 정확히 1만큼 클 때, 그 수를 '연속 숫자(Sequential Digits)'라고 합니다. 이번 글에서는 주어진 범위 [low, high]에 포함된 모든 연속 숫자를 오름차순으로 정렬된 리스트 형태로 구하는 방법을 알아보겠습니다.
예를 들어 low = 100, high = 300이 주어진다면, 이 범위 안에 속하는 연속 숫자는 123과 234 두 개뿐이므로 출력 결과는 [123, 234]가 됩니다.
알고리즘 접근 방식
이 문제는 가능한 모든 연속 숫자를 직접 생성한 뒤, 주어진 범위에 속하는 값만 걸러내는 완전 탐색 방식으로 해결할 수 있습니다. 연속 숫자는 최대 9자리(123456789)이고 시작 자릿수도 1~9 사이이므로 전체 경우의 수가 매우 적어, 이 방법으로도 충분히 효율적입니다.
단계별 풀이 과정은 다음과 같습니다.
- 결과를 저장할 배열 ans를 생성합니다.
- i를 1부터 9까지 반복합니다. i는 생성할 숫자의 자릿수입니다.
- j를 1부터 시작하여 j + i − 1 ≤ 9를 만족하는 동안 반복합니다. j는 연속 숫자의 첫 자릿수입니다.
- x를 0으로 초기화한 후, k를 0부터 i−1까지 반복하면서 x = 10x + (j + k)를 누적하여 연속 숫자를 만듭니다.
- 생성된 값 x가 low ≤ x ≤ high 조건을 만족하면 ans에 추가합니다.
- 모든 반복이 끝나면 ans를 반환합니다.
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;
}
class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector <int> ans;
for(int i = 1; i <= 9; i++){
for(int j = 1; j + i - 1 <= 9; j++){
int x = 0;
for(int k = 0; k < i; k++){
x = (x*10) + (j + k);
}
if(low <= x && x <= high){
ans.push_back(x);
}
}
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.sequentialDigits(500, 5000));
}
실행 결과
입력
500 5000
출력
[567, 678, 789, 1234, 2345, 3456, 4567]
500 이상 5000 이하 범위에는 세 자리 연속 숫자인 567, 678, 789와 네 자리 연속 숫자인 1234, 2345, 3456, 4567이 모두 포함되어 있음을 확인할 수 있습니다.