문제 풀이 최적화
하노이의 탑 문제와 마찬가지로 모음 사전 문제 또한 리스트를 이용하여 기록하는 문제입니다. 매 부분 문제마다 불필요한 리스트를 복사하는 것을 막고자 하노이의 탑 문제에서 적용했던 것과 같은 방식을 이용하여 최적화할 수 있습니다.
전체 코드
5장/모음_사전_최적화.java
import java.util.ArrayList;
import java.util.List;
public class Solution {
private static final char[] CHARS = "AEIOU".toCharArray();
private void generate(String word, List<String> words) {
words.add(word);
if (word.length() == 5) return;
for (char c : CHARS) {
generate(word + c, words);
}
}
public int solution(String word) {
List<String> words = new ArrayList<>();
generate("", words);
return words.indexOf(word);
}
}
이 장에서는 재귀를 알아보았습니다. 재귀는 앞으로 살펴볼 많은 부분에서 계속해서 활용하므로 반드시 익혀 두어야 할 개념입니다. 처음에는 코드 작성 없이 상태, 종료 조건, 점화식을 정의하는 것을 연습하여 익숙해지도록 합시다. 이후 명확하게 재귀를 정의할 수 있다면 간단하게 코드로 옮길 수 있을 것입니다.