LeetCode: 91번 (Decode Ways) [JAVA]

문제 링크

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

Decode Ways - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 메모제이션을 위한, 주어진 문자열 s 길이만큼의 int 배열 생성 후, 모든 요소를 -1로 초기화
2. 재귀 기반의 탐색 함수를 구현 (인자로는 s 속 특정 위치를 나타내는 index, 문자열 s)
   1) 주어진 index가 s의 길이를 넘으면 1 반환
   2) 메모제이션의 index 위치에 탐색 결과가 존재하면 해당 값 반환
   3) s 속 현재 위치의 문자가 '0'가 아니라면, 다음 위치를 인자로 동일 함수를 call한 다음 그 결과를 저장
   만약 '0'이라면 더 이상의 탐색이 불가능이므로 결과 0 반환
   4) 그 다음 위치의 문자를 추가하고, 여태까지의 문자열을 숫자로 변환한 결과가 10~26 사이의 숫자라면 그 다음 위치를 인자로 하는 함수의 결과를 저장
   5) 누적된 결과를 메모제이션 배열에 저장하며 반환
3. 위치 0, 문자열 s를 인자로 하는 재귀함수 결과를 반환

 기본적으로는 재귀 기반의 함수를 통해 문제를 해결해나가며, 메모제이션을 적용해 탐색 시간을 절약할 수 있다. 주어진 숫자 문자열을, 만들어질 수 있는 알파벳 형태 문자열의 가짓수를 반환하면 되기 때문에 재귀 기반으로 다음 탐색 함수를 call하며 결과를 누적해 반환하면 된다.
 우선 알파벳은 숫자 1~26 사이에서만 매핑이 되기 때문에, 문자열 s 속 특정 위치로부터 숫자를 가져올 땐 길이 1과 2의 부분 문자열만 신경쓰면된다. 그리고 길이 1의 숫자라면 0은 무조건적으로 불가능이고, 길이 2의 숫자라면 10~26 사이의 숫자여야만 한다.
 이를 바탕으로 재귀 함수를 구현하면 다음과 같다. 우선 인자는 s 속 특정 위치를 나타내는 index와 문자열 s를 가진다. 만약 index가 s의 길이를 넘어선다면 1을 반환한다. 이후 탐색 결과들을 저장할 result를 0으로 초기화한다. 그 다음 index 위치의 문자를 가져와서 판별을 하는데, 만약 해당 문자가 '0'이 아니라면 index+1을 인자로 하는 동일 함수를 call하고 그 결과를 result에 추가한다. 만약 반대로 '0'이라면 더 이상의 탐색이 불가능하기 때문에, 0을 반환한다. 그리고나서는 index+1 위치의 문자를 추가해 숫자로 변환한다. 만약 변환한 숫자가 10~26사이의 숫자라면 이는 추가 탐색이 가능하기 때문에, index+2를 인자로 하는 동일함수를 call하고 그 결과를 result에 추가해주면 된다. 이후 탐색 결과가 누적된 result를 반환하면 된다.
 전체 문제에서는, 주어진 s에 대해 시작 위치(0)부터 시작하는 재귀함수를 call해주고 그 결과를 반환하면 된다. 물론 여기서 탐색 시간을 줄이기 위해, 메모제이션을 적용할 수도 있다.

 

class Solution {
    int[] acc;

    public int numDecodings(String s) {
        acc = new int[s.length()];
        Arrays.fill(acc, -1);
        return recursive(0, s);
    }

    public int recursive(int index, String s) {//재귀 기반 판별
        if (index >= s.length()) {//인덱스가 문자열의 길이를 넘으면
            return 1;
        }

        if (acc[index] != -1) {//기존 탐색 결과가 있다면
            return acc[index];
        }

        int result = 0;

        StringBuilder sb = new StringBuilder();
        sb.append(s.charAt(index));

        if (!sb.toString().equals("0")) {//현재 위치의 문자가 0이 아니라면
            result += recursive(index + 1, s);
        } else {//0이면 이후엔 더 이상 불가
            return acc[index] = 0;
        }

        if (index + 1 < s.length()) {//다음 위치의 문자를 추가
            sb.append(s.charAt(index + 1));
            int num = Integer.parseInt(sb.toString());

            if (10 <= num && num <= 26) {//10~26 사이의 숫자라면
                result += recursive(index + 2, s);
            }
        }

        return acc[index] = result;
    }
}

결과