본문으로 건너뛰기

967 - Numbers With Same Consecutive Differences

info

풀이 키워드​

스포주의

백트래킹 dfs


풀이 코드​

info
  • 메모리: 42220 KB
  • 시간: 2 ms
import java.util.*;

class Solution {
    List<Integer> ansList = new ArrayList<>();
    int _n, _k;

    public void rcs(int num, int depth) {
        if (_n == depth) {
            ansList.add(num);
            return;
        }

        int lastDigit = num % 10;
        int cand1 = lastDigit - _k;
        int cand2 = lastDigit + _k;
        if (0 <= cand1) rcs(num*10+cand1, depth+1);
        if (cand1 < cand2 && cand2 < 10) rcs(num*10+cand2, depth+1);
    }

    public int[] numsSameConsecDiff(int n, int k) {
        _n = n;
        _k = k;
        for (int i = 1; i < 10; ++i) rcs(i, 1);

        return ansList.stream().mapToInt(i->i).toArray();
    }
}

풀이 해설​

전형적인 dfs 문제인데 이런것도 백트래킹이라 하더라.

시간복잡도가 2n2^n 인데 n≤9n \le 9 라서 무난하게 bfs로도 구현이 가능하다.

하지만 자바에서 큐를 꺼내쓰는 것이 여간 귀찮은게 아니라서 dfs로 접근했다.

num의 맨 뒤에 숫자를 붙여나가는 형식이므로 10을 곱해서 앞으로 밀고 k 조건에 맞는 숫자만 더해주면 된다.

int lastDigit = num % 10;
int cand1 = lastDigit - _k;
int cand2 = lastDigit + _k;
if (0 <= cand1) rcs(num*10+cand1, depth+1);
if (cand1 < cand2 && cand2 < 10) rcs(num*10+cand2, depth+1);

메모​

  • 다시 풀어보기보단 그냥 슥 읽어보고 넘어가면 될 것 같다.