[NeetCode-LeetCode] Decode Ways JAVA

반응형

728x90

[NeetCode-LeetCode] Decode Ways - Medium 

---

접근

• dp

---

풀이

숫자를 문자로 해독할 때 해독한 문자열이 몇 가지로 표현할 수 있는지 구하는 문제이다. 숫자는 1부터 26까지 알파벳과 매칭되고 26을 넘어가는 경우 27이 아닌 2와 7로 나눠져 해석된다. 그렇다 보니 10~26 사이의 숫자들도 나눠서 해석될 수 있다. 17이라는 숫자가 있는 경우 17로 해석되어 q가 될 수 도 있고 1과 7로 나눠져 ag로 해석이 될 수 도 있기 때문에 이렇게 해석될 수 있는 모든 경우의 수를 구해야 한다. 

 

dp 문제로 앞에서부터 체크하며 값을 쌓아나간다.

    public int numDecodings(String s) {
        if (s == null || s.isEmpty() || s.charAt(0) == '0') {
            return 0; 
        }

        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;  
        dp[1] = 1;

 

문자열이 비어있거나 맨 앞 숫자가 0인 경우 0을 반환한다. 0이 숫자 가운데 들어가는 경우 10이나 20의 뒷자리로 사용이 가능하지만 01과 같이 0이 앞에 오는 경우는 허용하지 않기 때문에 처리를 해준다. dp 배열을 만들어 초기화해 준다. dp 배열의 0번지는 빈 문자열의 경우이고 1번지의 경우는 한 개의 숫자가 존재하는 경우로 둘 다 1로 초기화시켜 준다.

	for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }

            int two = Integer.parseInt(s.substring(i - 2, i));
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }

 

 

i는 2인 세 번째 숫자부터 반복을 시작하게 되는데 dp 배열의 인덱스를 맞추기 위함이라 생각하면 되고 실제처리는 첫 번째, 두 번째 0, 1 인덱스에 대한 처리가 dp [2] 번에 저장된다고 보면 된다. 1번 인덱스의 숫자가 0이 아니라면 dp [1] 번에 저장된 1번까지의 경우의 수를 dp [2] 번에 더해준다. 그리고 두 자리 숫자에 대한 경우도 검사를 해야하기 때문에 substring으로 [0~1] 번까지를 잘라 두 자리 수로 만들어 유효한 범위 내에 있다면 해당 두 자리 수를 알파벳으로 변환이 가능하기 때문에 0번 인덱스의 경우의 수도 dp[2]번에 더해주게 된다. 이 과정은 s [i-1]과 s [i-2]를 두 자리 수로도 표현이 가능하다면 각각 한 자리 수로 표현하는 경우의 수도 더해주는 과정인 것이다.

---

전체 코드

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.isEmpty() || s.charAt(0) == '0') {
            return 0; 
        }

        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;  
        dp[1] = 1;  

        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }

            int two = Integer.parseInt(s.substring(i - 2, i));
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}