[LeetCode] - 1291. Sequential Digits

https://leetcode.com/problems/sequential-digits/description/

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Sequential Digits

문제 유형 : 구현

문제 난이도 : Medium

 

문제

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

 

정수의 각 자릿수들이 이전 자릿수보다 1씩 더 크면 sequential digits라고 한다.

[low, high]범위에 있는 모든 sequential digits를 담아서 정렬해서 반환하라.

 

 

풀이

반복문을 이용하여 쉽게 구현할 수 있다. DFS를 이용할 수도 있다.

for문으로 1부터 9까지 시작하고,

내부 while문으로 조건(수가 범위내에 있고, 다음 올 숫자가 9 이내인 동안)을 만족하는 동안 이전 숫자에서 10을 곱하고, 다음 숫자를 더해서 자릿수를 추가해준다.

다음 숫자는 계속 1씩 늘려주면 되고, 범위 안에 숫자가 있다면, 배열에 넣어주면 된다.

배열을 정렬하여 반환한다.

 

다른 풀이: 자릿수를 이용한 구현

최소 자릿수부터 베이스 숫자를 만든다(3자릿수의 베이스는 123)

만약 이 숫자가 범위에 있으면, 배열에 추가한다.

다음은, 숫자의 맨 앞을 제거하고, 뒤에는 기존 맨 뒤에서 1 더 큰수를 붙인다. 이를 맨 뒤의 숫자가 9가 될 때까지 한다.

만약 숫자가 범위에 있으면 배열에 추가하고, high보다도 크면 탈출한다.

배열을 정렬하여 반환한다.

 

코드

C++

// 컴파일 최적화 및 부스트..
#pragma GCC optimize("03", "unroll-loops");

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;
        for(int i = 1; i <= 9; i++) {
            int num = i;
            int next = i+1;
			
            // 현재 숫자가 범위 내에 있고, 다음 붙을 숫자가 유효한 동안
            while(num <= high && next <= 9) {
                num = num*10 + next;
                if(num >= low && num <= high) ans.push_back(num);
                next++;
            }
        }

        sort(ans.begin(), ans.end());
        return ans;
    }
};

 

 

자릿수별로 생성하는 풀이

class Solution {
public:
    void generate_seq(int low, int high, int min_digit, int max_digit, vector<int>& ans) {
        for(int i = min_digit; i <= max_digit; i++) {
            string num = "";
            // 베이스 숫자 만들기
            for(int j = 1; j <= i; j++) {
                num += to_string(j);
            }

            if(stoi(num) >= low && stoi(num) <= high) ans.push_back(stoi(num));

			// 맨 앞 숫자는 pop하고, 맨 뒤에 1 더큰수 Push
            for(int j = i+1; j <= 9; j++) {
                num = num.substr(1, num.size()-1);
                num += to_string(j);

                if(stoi(num) < low) continue;
                else if(stoi(num) > high) break;

                ans.push_back(stoi(num));
            }
        }
    }

    vector<int> sequentialDigits(int low, int high) {
        int min_digit = log10(low)+1;
        int max_digit = high == 1e9? 9 : log10(high)+1; // max num handling: if 1e9, max digit must be 9, not 10.

        vector<int> ans;
        generate_seq(low, high, min_digit, max_digit, ans);
        sort(ans.begin(), ans.end());

        return ans;
    }
};