본문으로 건너뛰기

1641. Count Sorted Vowel Strings

· 약 2분
Seokjae Lee
Seokjae Lee
Software engineer

원문: https://doljae.tistory.com/228

[Count Sorted Vowel Strings - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com](https://leetcode.com/problems/count-sorted-vowel-strings/)

양의 정수 N이 주어질 때, 알파벳 소문자 모음 5개로 길이 N의 문자열을 만들고 그 가짓수를 반환한다.

이때 문자열을 구성하는 문자들은 사전 순으로 오름차순 정렬돼있는 문자열만 인정한다.

예시

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

접근법​

입력되는 N은 최대 50이다. DFS로도 풀 수 있을 것 같은데...

하지만 재귀 없이 선형 탐색 정도의 시간 복잡도로도 문제를 해결할 수 있을 것 같았다.

1. 규칙을 이용한 구현​

class Solution:
    def countVowelStrings(self, n: int) -> int:
        a, e, i, o, u = [1], [1], [1], [1], [1]

        for index in range(2, n + 1):
            a.append(a[-1] + e[-1] + i[-1] + o[-1] + u[-1])
            e.append(e[-1] + i[-1] + o[-1] + u[-1])
            i.append(i[-1] + o[-1] + u[-1])
            o.append(o[-1] + u[-1])
            u.append(u[-1])

        return a[-1] + e[-1] + i[-1] + o[-1] + u[-1]

규칙은 다음과 같다.

  1. 어떤 문자열이 사전 순으로 정렬되어있다면 그 문자열의 부분 문자열도 사전 순 정렬되어있다.
  2. 즉 어떤 문자 X로 시작하는 길이 N의 사전 순사 전 순 문자열의 종류는 "X" + X로 시작하는 길이 (N-1)의 사전 순 문자열이다.
    1. "a"로 시작하는 길이 2의 사전 순 문자열의 종류는 "a" + "a"로 시작하는 길이 (2-1 = 1)의 사전 순 문자열이다.
    2. "a"+ { "a", "e", "i", "o", "u" }

이 규칙으로 길이 2인 경우도 위의 예시와 비교해보면 적용할 수 있다는 것을 알 수 있다.

 그럼 위에서 얻은 점화식을 코드로 그대로 구현하면 해결할 수 있다.