[리트코드] 1291 - Sequential Digits

1291. 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.

 

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] 안에 존재하는 **순차적인 숫자(Sequential Digits)**를 모두 찾아 정렬된 리스트로 반환하는 것입니다. 순차적인 숫자란, 각 자릿수가 이전 자릿수보다 정확히 1 큰 숫자를 의미합니다. (예: 123, 2345, 6789) 입력은 두 정수 low와 high이며, 제약 조건은 10 <= low <= high <= 10^9입니다. 출력은 조건을 만족하는 정수들의 리스트입니다.

접근 방법

이 문제는 완전 탐색(Brute Force) 또는 생성(Generation) 방식을 사용하여 해결합니다. 가능한 모든 순차적인 숫자의 개수가 매우 적다는 점이 핵심입니다. 가장 긴 순차적인 숫자는 123456789 (9자리)이며, 시작 숫자(19)와 길이(29)를 조합해 만들 수 있는 경우의 수는 최대 36개(9+8+...+1)에 불과합니다. 따라서 low부터 high까지 모든 숫자를 검사하는 대신, 만들 수 있는 모든 순차적인 숫자를 미리 생성한 뒤 범위 내에 있는 것만 필터링하는 방식이 훨씬 효율적입니다.

구현 설명

1. 시작 숫자 순회

for i in range(1, 10):

순차적인 숫자의 첫 번째 자릿수는 1부터 9까지 가능합니다. 0으로 시작할 수 없고, 9로 시작하면 다음 숫자(10)가 한 자릿수가 아니므로 순차적인 숫자를 만들 수 없습니다. 따라서 1부터 9까지 각 숫자를 시작점(i)으로 하여 순차적인 숫자를 생성합니다.

2. 숫자 확장 및 생성

s = i
total = s
while s < 9:
    s += 1
    total = 10 * total + s

현재 시작 숫자 i를 변수 s와 total에 저장합니다. while 루프를 통해 s가 9보다 작을 동안 다음 숫자(s+1)를 뒤에 붙여나갑니다. total = 10 * total + s 연산은 기존 숫자 total을 한 자리 왼쪽으로 밀고(10을 곱함), 새로운 숫자 s를 일의 자리에 더하는 효과를 냅니다. (예: 12 -> 12*10+3 = 123)

3. 범위 확인 및 조기 종료

if total > high:
    break
if low <= total:
    answer.append(total)

생성된 숫자 total이 high를 초과하면, 더 이상 자릿수를 늘려도 숫자는 커지기만 하므로 break를 통해 현재 시작 숫자 i에 대한 루프를 즉시 종료합니다. (가지치기/Pruning) low 이상 high 이하 범위에 들어오면 정답 리스트 answer에 추가합니다.

4. 결과 정렬 및 반환

return sorted(answer)

시작 숫자(1~9) 순서대로, 길이가 짧은 것부터 긴 순서대로 생성되지만, 숫자 크기 순서와 완벽히 일치하지 않을 수 있습니다. (예: 시작 숫자 2로 만든 234가 시작 숫자 1로 만든 1234보다 작음) 따라서 최종적으로 sorted()를 호출하여 오름차순으로 정렬된 리스트를 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(1) 생성 가능한 순차적인 숫자의 총 개수는 고정되어 있습니다. (12, 123, ..., 123456789, 23, 234, ... 등 총 36개) 입력 값 low, high에 관계없이 최대 36번의 연산만 수행하므로 상수 시간입니다. 정렬 또한 최대 36개 원소에 대한 것이므로 O(1)입니다.
• 공간 복잡도: O(1) 정답 리스트 answer에 저장되는 원소의 최대 개수 역시 36개로 고정되어 있으므로 상수 공간을 사용합니다.

핵심 포인트

1. 검색 공간의 한정: 10^9 이하의 순차적인 숫자는 총 36개뿐이므로, 범위 내 모든 숫자를 검사하지 않고 가능한 숫자만 생성하는 방식이 최적입니다.
2. 숫자 생성 로직: total = total * 10 + next_digit 공식을 이용해 문자열 변환 없이 정수 연산만으로 효율적으로 숫자를 늘려갑니다.
3. 가지치기(Pruning): 생성 중인 숫자가 high를 넘으면 즉시 루프를 종료(break)하여 불필요한 연산을 줄입니다.

풀이 코드

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        answer = []
        for i in range(1,10):
            s = i
            total = s
            while s < 9:
                s += 1
                total = 10*total + s

                if total > high:
                    break

                if low <= total:
                    answer.append(total)

        return sorted(answer)