[LeetCode]Count Sorted Vowel Strings

새벽에 적느라 풀이 설명이 엉망이었어서 수정하였다

풀이 생각

• 백트랙킹을 생각했다.
• a는 index 0, e는 index1로 생각하여 ,
  • for문을 도는데 이전의 index이상만 선택가능하게 하였고
  • 현재 호출된 함수의 an이 n과 같으면 1을 리턴하도록 하여
  • 수를 세는 방법을 하였다.

class Solution {
    /*
    n개의 정수가 주어졌을 때 . 
    길이 n을 가진 문자열의 개수를 리턴한다. 
    이 때 이 문자열은 : 모음 a,e,i,o,u로 만 이루어져있어야 하며, lexicographically 정렬되어있어야 한다. 
    lexicographically정렬되어있다는게 무슨 말이냐면
    문자열의 각 character에 대한 index i 일 때, 모든 i에 대하여 
    s[i]가 알파벳상으로 s[i+1]보다 이전 또는 같은 알파벳인것을 말한다. 
    ======
    생각해보면
    ======
    n이 1이상 50 이하다. 
    ======
    1. 단순하게 생각한다면 
    - 각 자리에 a,e,i,o,u의 5가지 알파벳이 올 수 있다 
    - i에 e가 온다면 i+1부터는 4가지 알파벳이 올 수 있다. 
    - i에 i가 온다면, i+1부터는 3가지 알파벳이 올 수 있다. 
    - i에 o가 온다면, i+1부터는 2가지 알파벳이 올 수 있다. 
    
    =====
    2. 
    */
    public int gn;
    public int countVowelStrings(int n) {
        gn=n;
        return solve(0,0);
        
    }
    
    public int solve(int i,int an){
        if(an==gn)return 1; 
        int sum=0;
        for(int cur=i;cur<5;cur++){
            sum+=solve(cur,an+1);
        }    
        return sum;
    }
}

내 풀이 → 복잡도가 최악이다.

• 나는 단순히 백트랙킹을 사용하려 했다.

다른 방법 → DP를 사용하여 풀이 - pattern파악이 중요하다

참고풀이영상(영어)

a,e,i,o,u로 시작 하는 것의 개수를 저장하는 cache가 존재한다고 하자.

---

• 예시
  n=1일 때
  a e i o u → 1,1,1,1,1
  n=2일 때
  aa ae ai ao au →5,4,3,2,1

  ee ei eo eu
  
  ii io iu 
  
  oo ou 
  
  uu

  n=3일 때 a로 시작하는 것만 먼저 해 보면
  aaa aae aai aao aau

  aee aei aeo aeu
  
  aii aio aiu
  
  aoo aou
  
  auu
  이다 
  eee eei eeo eeu
  
  ......

---

즉,

n=1 -> 1 1 1 1 1
n=2 -> 5 4 3 2 1
n=3 -> 15 10 6 3 1

n=1 일 때부터 n의 값을 증가시키면서,

x로 시작하는 string의 개수를 세어 놓는다면

n이 증가했을 때, x로 시작하는것의 개수를 구하기 위해서는, 이전의 n일 때 , x보다 lexicographically하게 뒤에 있는 또는 같은 알파벳으로 시작하는 것의 개수들을 모두 더한 것이 된다.

• 왜냐하면 예를들어 n이 3일 때 e로 시작하는 것은 결국, 남은 두 개의 글자에 대한 경우의 수를 생각해보면, 이에 대한 것은 n=2 일 때, e로 시작하는 string의 개수 + (사전상 e다음인) i, o,u 로 시작하는 string의 개수들의 합과 같기 때문

class Solution {
    
    
    public int countVowelStrings(int n) {
        int[] alp = new int[]{1,1,1,1,1};
        if(n==1)return 5; 
        int cur=2;
        int sum=0;
        int i=0,pre=0;
        while(cur<=n){
            // cur이 2라는 것은, 현재 n이 2인 상황에 대한 것 
            // alp[i]자체가, n= cur-1일 때에, x로 시작하는 string의 개수 이니 pre는 i+1로시작
            for(i=0;i<alp.length;i++){
                for(pre=i+1;pre<alp.length;pre++)  alp[i]+=alp[pre];
            }
            cur++;
        }
        for(i=0;i<alp.length;i++)
            sum+=alp[i];
        return sum;
    }
}