LeetCode 일일 문제 - 967. 동일한 연속 차이가 있는 숫자

문제

연속된 두 자릿수 사이의 절대 차이가 k가 되도록 길이가 n인 모든 음수가 아닌 정수를 반환합니다.

답변의 모든 숫자 앞에 0이 있어서는 안 됩니다. 예를 들어 01은 앞에 0이 하나 있고 유효하지 않습니다.

어떤 순서로든 답변을 반환할 수 있습니다.

아이디어

이를 해결하는 방법은 숫자를 숫자 단위로 구성하는 것입니다. 1에서 9까지의 숫자x를 첫 번째 숫자로 선택할 수 있습니다. 숫자를 선택하면 최대 두 가지 유효한 선택x + k 및 x - k가 있습니다. 즉, 둘 다 [0, 9]에 있습니다. 그런 다음 문제는 구조가 유사한 더 작은 문제, 즉 모든 단계에서 숫자가 하나 적은 문제를 해결하는 것으로 축소됩니다. n개의 숫자가 선택되면 응답 배열에 숫자를 추가할 수 있습니다.

해결책

class Solution {
    public void dfs (int NumOfDigits, int currNum, int k, List<Integer> ans) {
        if (NumOfDigits == 0) {
            ans.add(currNum);
            return;
        }

        List<Integer> nextDigits = new ArrayList<>();

        int tailDigit = currNum % 10;
        nextDigits.add(tailDigit + k);
        if(k != 0) {
            nextDigits.add(tailDigit - k);
        }

        for(int nextDigit : nextDigits) {
            if(0 <= nextDigit && nextDigit < 10) {
                int num = currNum * 10 + nextDigit;
                dfs(NumOfDigits - 1, num, k, ans);
            }
        }
    }

    public int[] numsSameConsecDiff(int n, int k) {
        if (n == 1) {
            return new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        }

        List<Integer> ans = new LinkedList<Integer>();

        for (int i = 1; i < 10; i++) {
            dfs(n - 1, i, k, ans);
        }

        return ans.stream().mapToInt(i -> i).toArray();

    }
}

런타임: 9ms, Numbers With Same Consecutive Differences에 대한 Java 온라인 제출의 21.14%보다 빠릅니다.

메모리 사용량: 44.2MB, Numbers With Same Consecutive Differences에 대한 Java 온라인 제출의 6.62% 미만.

참고 - 재귀 스택을 처리할 필요가 없기 때문에 이 문제의 BFS 솔루션은 메모리 효율성이 훨씬 뛰어납니다.