2021-01-17] Count Sorted Vowel StringsSolution

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3607/

Explore - LeetCode

 

실은 어제의 문제.. 날짜별로 푸는 문제라...ㅎㅎ 어쩔수가 없다

 

나에겐 이 문제는 실패했던 문제이다.. 그래서 늦게올린거니 양해바람돠..

 

문제예시

문제예시 1-3

문제에선 vowel 안에 주어지는 문자들이 입력받는 n에 대해서 문자열의 길이가 n개인 문자열이 몇개인지 찾는 문제

n개의 문자열이 '사전적으로 정렬되게끔' 해야한다 예시 2번을 보면 이해할 수 있다.

n=2일때, vowels 의 문자5개로 만들수 있는 문자열은

a : a'a', a'e', a'i', a'o', a'u;  = 5

e : e'a'=X ( 사전적으로 a가 e보다 빠르기에 올수없다 )  e'e', e'i', e'o', e'u' = 4

i : i'i', i'o', i'u' = 3

o : o'o', o'u'= 2

u : u'u' =1 

즉 문자열 길이 2개로 만들수 있는 문자열 개수는 5+4+3+2+1 = 15 이다.

 

3개의 경우 a: 15 / e: 10 / i: 6 / o: 3 / u: 1 =15  개이다.

 

아래와 같이 수학적으로 풀 수 있다. ( 내가 구하진 못하였고, 동기가 구했다.. )

 

class Solution: 
    def countVowelStrings(self, n: int) -> int: 
        arr = [1,1,1,1,1]  # vowels 값이라고 생각하자. 어차피 count하는거라 1로 표현
        if n == 1: 
            return sum(arr)  # n==1일 때, 각 하나씩만 존재하고 그 합을 구하면 된다.
        for _ in range(1,n):  # n >=2일 때, 총 n 회차 반복 
            for i in range(4,-1,-1):  # 마지막 값 부터 합을 채워야한다. ( 5,4,3,2,1 처럼 )
                arr[i] = sum(arr[:i+1])  # n=2 1+4(1+1+1+1)  / 1+3(1+1+1) / 1+2(1+1) / 1+1 / 1
                                         # n=3 5+10(4+3+2+1) / 4+6(3+2+1) / 3+3(2+1) / 2+1 / 1
                                         # ...
        return sum(arr)