박종훈 알고리즘 블로그

(Leetcode) 91 - Decode Ways 풀이


기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice


https://leetcode.com/problems/decode-ways/description/

dfs를 통한 모든 경우의 수 탐색하기

일단 가장 단순하게 접근해보았다. 해보면 시간 초과로 실패한다.

class Solution {
    public int numDecodings(String s) {
        Counter counter = new Counter();
        dfs(counter, s, 0, 1);
        dfs(counter, s, 0, 2);
        return counter.counter;
    }

    public void dfs(Counter counter, String s, int start, int end) {
        if(end > s.length()) {
            return;
        }

        String substring = s.substring(start, end);
        int value = Integer.parseInt(substring);
        if (value <= 0 || value > 26 || substring.startsWith("0")) {
            return;
        }

        if (end == s.length()) {
            counter.increment();
        }

        dfs(counter, s, end, end + 1);
        dfs(counter, s, end, end + 2);
    }
}

class Counter {
    int counter = 0;

    void increment() {
        counter++;
    }
}

규칙성으로 풀기 (DP)

우리가 각 자리에서 고려할 수 있는 케이스는 2가지이다. 한 자리를 선택할지, 두 자리를 선택할지이다.

각 자리까지의 경우의 수를 dp 배열에 저장한다.

첫번쨰 자리는 하나밖에 선택하지 못한다. 맨 앞자리가 0인 경우는 불가능이다. 따라서 0을 반환해주고 그 외의 경우에는 1을 넣어준다. (dp[0] = 1)

그 이후부터가 조금 복잡하다.

우선 해당 수가 0보다 큰 자리인지를 확인한다. 0보다 크다면 혼자서 선택이 가능하다. 이 경우 앞 자리(n-1)의 경우의 수를 물려받는다. (dp[i] = dp[i - 1]) 앞의 수가 무엇이 되었든 혼자서 독립적으로 선택이 가능하다.

이제 두 숫자를 묶어서 선택하는 케이스를 고려해보자. 이 경우에는 앞자리가 0이면 불가능 하다. (prevDigit == 0) 문제에 있는 06 이 이 케이스에 속한다. 그리고 두 자리를 선택했을 때 26보다 작거나 같아야 한다. (twoDigit <= 2) 27보다 큰 경우는 decode 될 수 없다. 만약 두 자리로 선택이 가능할 경우 n-2의 경우의 수를 물려받는다. 다만 앞에서 한자리 수를 선택했을 경우도 있기 때문에 기존의 dp[i] 에 더하기를 해준다. (dp[i] = dp[i] + dp[i - 2]) 예외적으로 만약 i가 1인 상태라면 이전의 케이스가 없다. 따라서 1을 더해준다. (dp[i] = dp[i] + 1)

class Solution {
    public int numDecodings(String s) {
        int[] dp = new int[s.length()];

        if (s.charAt(0) == '0') {
            return 0;
        }
        dp[0] = 1;

        for (int i = 1; i < s.length(); i++) {
            int oneDigit = Integer.parseInt(String.valueOf(s.charAt(i)));
            if (oneDigit > 0) {
                dp[i] = dp[i - 1];
            }

            int prevDigit = Integer.parseInt(String.valueOf(s.charAt(i - 1)));
            if (prevDigit == 0) {
                continue;
            }

            int twoDigit = prevDigit * 10 + oneDigit;
            if (twoDigit <= 26) {
                if (i > 2) {
                    dp[i] = dp[i] + dp[i - 2];
                } else {
                    dp[i] = dp[i] + 1;
                }
            }
        }

        return dp[s.length() - 1];
    }
}

TC, SC

시간 복잡도는 O(n), 공간 복잡도는 O(n)이다. 이런식으로 최근 데이터만 재사용 하는 경우에는 공간복잡도를 O(1) 으로도 줄일 수 있을 것이다. 최근의 데이터가 아닌 이전 데이터들은 더 이상 참조되지 않기 때문에 필요한 공간만 만들어서 보관하면 된다.