[LeetCode] 1291. Sequential Digits -문제풀이

Description

주어진 범위내의 정수 안에서 연속된 digit으로 구성된 가능한 모든 숫자를 반환하는 문제입니다.

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

Solution 1. substring()

List<Integer> sequentialDigits(int low, int high) {

    // 1. Using SubString
    List<Integer> result = new ArrayList<>();
    String str = "123456789";
    int len = 1;
    for (int i = 0; i < str.length(); i++) {
        for (int j = 0; j <= str.length()-len; j++) {
            int num = Integer.valueOf(str.substring(j,j+len));
            if(num >= low){
                if(num <= high){
                    result.add(num);
                }else{
                    return result;
                }
            }
        }
        len++;
    }
    return result;
}

가능한 경우의 수인 “123456789” 에서 1부터 9까지 len순으로 반복하며 범위를 벗어날 때까지 가능한 값을 찾아 나갑니다.

Solution 2. 너비 우선 탐색 (BFS, Breadth-First Search )

List<Integer> sequentialDigits(int low, int high) {

    // 2. BFS
    List<Integer> result = new ArrayList<>();
    Queue<Integer> q = new LinkedList<>(Arrays.asList(1,2,3,4,5,6,7,8,9));
    while(!q.isEmpty()){
        int cur = q.poll();
        if(cur > high){
            break;
        }
        if(cur >= low && cur <= high){
            result.add(cur);
        }
        int num = cur % 10;
        int next = cur * 10 +(num+1);
        if(num < 9) q.offer(next);
    }
    return result;
}
/* Silumation illustration on example 1 step-by-step
q={1,2,3,4,5,6,7,8,9},        ans={}, 1->12
q={2,3,4,5,6,7,8,9, 12},      ans={}, 2->23
q={3,4,5,6,7,8,9, 12, 23},    ans={}, 3->34
q={4,5,6,7,8,9, 12, 23,34},   ans={}
...
q={9,12,23,34,45,56,67,78,89},ans={}
...
q={12,23,34,45,56,67,78,89},  ans={}
...
q={23,34,45,56,67,78,89,123}, ans={123}
q={34,45,56,67,78,89,123,234},ans={123,234}
q={45,56,67,78,89,123,234,345},ans={123,234}, 345 > high=400, BREAK
*/

BFS(너비우선탐색)을 이용한 방법입니다. 1~9까지 큐에 먼저 넣고 가능한 다음 두자리 숫자부터 큐에 넣어가며 진행하는 방법입니다. 작은 수부터 가능한 수가 들어가기 때문에 별도 정렬이 필요하지 않습니다.

Solution 3. 전체 탐색(Brute Force)

public List<Integer> sequentialDigits(int low, int high) {

    // 1. Brute Force
    List<Integer> result = new ArrayList<>();

    for (int i = 1; i <= 9; i++) {
        StringBuilder sb = new StringBuilder();
        sb.append(i);
        for (int j = i+1; j <= 9; j++) {
            sb.append(j);
            int num = Integer.valueOf(sb.toString());
            if(num >= low && num <= high){
                result.add(num);
            }
        }
    }
    Collections.sort(result);
    return result;

}

범위안의 연속적으로 구성이 가능한 가능한 모든 경우의 수를 체크하여 정렬 후 반환해 줍니다.

Reference

Sequential Digits - LeetCode