Search
Duplicate
🎾

[DP] leetcode 1641. Count Sorted Vowel Strings 풀이

태그
Dynamic Programming
공개여부
작성일자
2021/01/07
어느정도 실마리를 잡았는데 실마리 잡은 상태로 1시간이 넘어가서 discuss를 보고 풀었다. 문제 난위도는 medium 이지만, 접근이 나름 쉬웠다. 다만 그 접근을 코드로 변경하는데 시간이 많이 쏟아진게 사실이다.

문제

Given an integer n, return the number of strings of length n that consist only of vowels (aeiou) and are lexicographically sorted.
A string s is lexicographically sorted if for all valid is[i] is the same as or comes before s[i+1] in the alphabet.
examples

접근방법

먼저 나올 수 있는 String 배열을 작성해봤다.
n = 2 이면 다음과 같다
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
Java
이것은 (aeiou) 두개의 조합이다
n=2n = 2
결과는 총 15개가 나온다.
n=3n = 3
이와 같이 매칭하여 결과는 총 35개가 나온다 (직접 세어봄)
이렇게 그리다보면 어떠한 규칙성을 발견하는데 그것을 table 로 표시하면 상당히 직관적이다.
n값 기준 a, e, i, o, u로 끝나는 개수
Name
a
e
i
o
u
n=2
Open
5
4
3
2
1
n=3
Open
15
10
6
3
1
n=4
Open
35
20
10
4
1
어떠한 문자열로 끝나는지가 중요하다.
그러면 여기서 유의미한 점화식을 구할 수 있다
모든 n 에 대한 a 의 값은 n-1 의 (aeiou) 의 합과 같다
dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + dp[n-1][3] + dp[n-1][4];
Java
그리고 dp[i][j] 의 값은 다음과 같다
dp[i][j] = dp[i][j-1] - dp[i-1][j-1];
Java
점화식이 나왔다면 base case 를 정의해야 한다.
dp[1] = new int[] {1, 1, 1, 1, 1}; dp[2] = new int[] {5, 4, 3, 2, 1}; dp[3][0] = 15; // sum(dp[2]);
Java
내가 푼 풀이는 다음과 같다
class Solution { int[][] cache = new int[52][5]; public int countVowelStrings(int n) { cache[1] = new int[] {1, 1, 1, 1, 1}; // 5 cache[2] = new int[] {5, 4, 3, 2, 1}; // 15 cache[3][0] = 15; for (int i = 3; i <= n; i ++) { int sum = 0; for (int j = 0; j < 5; j ++) { if (j == 0) { sum += cache[i][j]; continue; } cache[i][j] = cache[i][j-1] - cache[i-1][j-1]; sum += cache[i][j]; } cache[i+1][0] = sum; } return cache[n+1][0]; } }
Java
input 을 10으로 두었을때 cache 에 저장된 데이터
Runtime Error 가 발생한 이유는 Constraint 가 1 ≤ n ≤ 50 이기 때문에 최초에 cache 를 아래와 같이 정의했다
int[][] cache = new int[51][5];
Java
하지만 n을 구하기 위해 우리는 n+1 의 0번째 까지 알아야 한다
return cache[n+1][0];
Java
그래서 new int[52][5] 로 변경해야 했다.
O(n)O(n) 이지만, 공간도 좀 더 줄일 방법이 있을것 같다.
생각을 조금만 바꿔도 괜찮은것 같다. 표를 그려볼 생각을 못했다.
사실 n=3 까지 그리고 각 알파벳으로 끝나는 개수가 몇개인지 카운트 하는데 까지 갔지만 이것을 표로 그릴 생각을 못한게 아쉽다.. 생각의 도구를 추가하는 훈련이 필요하다.
TOP