leetcode 1291) Sequential Digits

LV. Medium 🧐

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

Sequential Digits - LeetCode

 

문제

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.

 

Example 1:

Input: low = 100, high = 300
Output: [123,234]

Example 2:

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

 

Constraints:

• 10 <= low <= high <= 10^9

 

문제 해결법

low와 high의 자릿수와 시작 숫자를 저장한다.

low의 자릿수, 시작 숫자를 사용해 수를 만들어 ans vector에 저장한다.

ex)
자릿수 : 4, 시작 숫자 : 5
num = 5678

위에 예제와 같이 num를 만들어 high보다 작으면 ans에 넣어준다.

num를 만드는 자릿수와 시작 숫자 둘 다 high를 넘어가면 만들어지는 num은 무조건 high보다 크기 때문에 while문을 빠져나오고 ans를 리턴해준다.

 

해결 코드

class Solution {
private:
    int start_digit;
    int start_num;
    int end_digit;
    int end_num;
    vector<int>ans;
    int create_num(int num, int digit) {
        int temp = 0;
        
        while (digit > 0) {
            temp += num * pow(10, digit - 1);
            num++;
            digit--;
        }
        return temp;
    }
public:
    vector<int> sequentialDigits(int low, int high) {
        int high_tmp = high;
        int low_tmp = low;
        start_digit = 1;
        end_digit = 1;
        while (low >= 10) {
            low = low / 10;
            start_digit++;
        }
        start_num = low;
        while (high >= 10) {
            high = high / 10;
            end_digit++;
        }
        end_num = high;
        
        while (1) {
            if (start_num > 10 - start_digit) {
                start_num = 1;
                start_digit++;
            }
            int temp = create_num(start_num, start_digit);
            if (temp > high_tmp)
                break;
            else if (temp >= low_tmp)
                ans.push_back(temp);
            start_num++;
        }
        return ans;
    }
};