[Java][LeetCode] #1641. Count Sorted Vowel String | O(n)

내가 너무나 약한 DP에서 랜덤으로 풀어보았다.

근데 DP로 푼지 아닌지 모르겠음

 

문제 / 예제 / 제한조건

 

풀이 

패턴을 찾느라고 거의 1시간은 쓴 것 같다.

뇌가 잘 안돌아가서 나는 직접 다 적어봐야 패턴을 찾을 수 있다..

뭐 경험이 부족한 탓이겠지!?

 

그렇게해서 찾은 패턴!

 

n = 1 일 때 각자 개수는

A	E	I	O	U
1	1	1	1	1

 

n = 2 일 때, 각각의 개수는

A	E	I	O	U
5	4	3	2	1

 

n = 3 일 때, 각각의 개수는

A	E	I	O	U
15	10	6	3	1

 

이렇게 구성되어 있다.

 

규칙이 보인다 +_+

바로바로

A	E	I	O	U
n=2 일때의 A + E + I + O + U	n=2 일때의 E + I + O + U	n=2 일때의  I + O + U	n=2 일때의  O + U	n=2 일때의  U
15	10	6	3	1

 

그렇게 구현해보면~

class Solution {
    public int countVowelStrings(int n) {
        int[] Aeiou = {1,1,1,1,1};
        for(int i=0; i<n; i++) {
            Aeiou[0] = Aeiou[0] + Aeiou[1]+ Aeiou[2]+ Aeiou[3]+ Aeiou[4];
            Aeiou[1] = Aeiou[1] + Aeiou[2]+ Aeiou[3]+ Aeiou[4];
            Aeiou[2] = Aeiou[2] + Aeiou[3]+ Aeiou[4];
            Aeiou[3] = Aeiou[3] + Aeiou[4];
        }

        return Aeiou[0];
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

 

깔끔한 결과를 볼 수 있다!

 

깔꿈깔꿈