문제 출처
https://leetcode.com/problems/count-sorted-vowel-strings(리트코드)
학습 키워드
동적계획법
시도 방법
규칙 발견 및 재귀 방식을 이용해 풀이
내가 작성한 코드
class Solution {
public int countVowelStrings(int n) {
return countVowels(n , 0);
}
public int countVowels(int n , int start) {
if(n==0) {
return 1;
}
int count = 0 ;
for(int i = start; i<5; i++) {
count += countVowels(n-1 , i);
}
return count;
}
}코드설명
문제에서 요구하는 상황은 아래 그림과 같으며 해당 n 자리수까지 일치하는 모음 배열의 개수를 구하는 것이다. 만약 n=2 라면 aa , ae , ai , ao , au ... uu 조합으로 총 15개가 나온다. 이런 규칙을 이용해 재귀를 풀이해보려 한다.
소스분석
public int countVowels(int n , int start) {
if(n==0) {
return 1;
}
int count = 0 ;
for(int i = start; i<5; i++) {
count += countVowels(n-1 , i);
}
return count;
}n=5라고 가정해보자.
countVowels(5 , 0) 으로 호출이 시작된다.
for문에서 0~4 (n-1) 까지 반복을 하면서 재귀호출을 하는데 다음과 같다.
n-1을 하는이유는 현재 선택한 문자를 제외한 나머지 길이를 의미하기 위함이다.
0~4를 a e i o u 라고 가정한다.
countVowels( 4 , 0 ) //a로 시작하는 경우
countVowels( 4 , 1 ) //e로 시작하는 경우
countVowels( 4 , 2 ) //i로 시작하는 경우
countVowels( 4 , 3 ) //o로 시작하는 경우
countVowels( 4 , 4 ) //u로 시작하는 경우
countVowels(4,0) 을 다시보면 아래와 같이 재귀된다.
countVowels(3,0)
countVowels(3,1)
countVowels(3,2)
countVowels(3,3)
countVowels(3,4)
countVowels(3,0) 을 다시보면 아래와 같이 재귀된다.
countVowels(2,0)
countVowels(2,1)
countVowels(2,2)
countVowels(2,3)
countVowels(2,4)
...
countVowels(1,0)
countVowels(1,0)
countVowels(1,0)
countVowels(1,0)
countVowels(1,0)
이후 n = 0 이 되는 순간 모든 모음조합을 의미하여 1을 리턴한다.
출력결과
새롭게 알게된 점
아직은 규칙을 찾고 이를 재귀적으로 풀어내는 동적계획법 문제가 좀 어려운 것 같다. 재귀의 규칙을 잘 맞추고 생각하면서 문제를 풀어야겠다.
다음에 풀어볼 문제 - count-square-submatrices-with-all-ones
#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL
