어느정도 실마리를 잡았는데 실마리 잡은 상태로 1시간이 넘어가서 discuss를 보고 풀었다. 문제 난위도는 medium 이지만, 접근이 나름 쉬웠다. 다만 그 접근을 코드로 변경하는데 시간이 많이 쏟아진게 사실이다.
문제
Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.
A string s is lexicographically sorted if for all valid i, s[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
복사
이것은 (a, e, i, o, u) 두개의 조합이다
결과는 총 15개가 나온다.
이와 같이 매칭하여 결과는 총 35개가 나온다 (직접 세어봄)
이렇게 그리다보면 어떠한 규칙성을 발견하는데 그것을 table 로 표시하면 상당히 직관적이다.
어떠한 문자열로 끝나는지가 중요하다.
그러면 여기서 유의미한 점화식을 구할 수 있다
모든 n 에 대한 a 의 값은 n-1 의 (a, e, i, o, u) 의 합과 같다
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] 로 변경해야 했다.
이지만, 공간도 좀 더 줄일 방법이 있을것 같다.
생각을 조금만 바꿔도 괜찮은것 같다. 표를 그려볼 생각을 못했다.
사실 n=3 까지 그리고 각 알파벳으로 끝나는 개수가 몇개인지 카운트 하는데 까지 갔지만 이것을 표로 그릴 생각을 못한게 아쉽다.. 생각의 도구를 추가하는 훈련이 필요하다.
