(Leetcode) 91 - Decode Ways 풀이
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
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) 으로도 줄일 수 있을 것이다. 최근의 데이터가 아닌 이전 데이터들은 더 이상 참조되지 않기 때문에 필요한 공간만 만들어서 보관하면 된다.