TIL 1일차

https://school.programmers.co.kr/learn/courses/30/lessons/84512

재귀함수로 문제 풀기

1. 먼저 상태가 나타내는 부분 문제를 해결하는 generate() 메서드를 작성한다.
이 부분 문제는 word로 시작하는 모든 단어를 구해야 하므로 List를 반환한다.

private List<String> generate(String word) {
	//	종료 조건, 점화식 구현
}    

2. 종료 조건은 word 길이가 5일 때 바로 word를 반환하는 것이다. 다음과 같이 구현할 수 있다.

private List<String> generate(String word) {
	List<String> words = new ArrayList<>();
    words.add(word);
    
    if (word.length() == 5) return words;
    
    // 점화식 구현
}    

3. 마지막으로 점화식은 사용할 수 있는 모든 문자를 word에 이어 붙여야 한다. 
사용할 수 있는 문자들을 클래스의 맨 위에 선언해주고, 이를 이용하여 재귀를 진행한다.

public class Solution {
	private static final char[] CHARS = "AEIOU".toCharArray();
    
    private List<String> generate(String word) {
		List<String> words = new ArrayList<>();
    	words.add(word);
    
    	if (word.length() == 5) return words;
    
   	 	for (char c : CHARS) {
    		words.addAll(generate(word + c));
   		}
    	return words;
    }

4. solution() 메서드에서는 generate() 메서드를 사용하여 정렬된 단어의 리스트를 얻고, 이 리스트에서 word가 몇 번째인지 구하면 된다.

public int solution(String word) {
	return generate("").indexOf(word);
}    

정리하면 전체 코드는 아래와 같다.

import java.util.ArrayList;
import java.util.List;

public class Solution {
	private static final char[] CHARS = "AEIOU".toCharArray();
    
    private List<String> generate(String word) {
		List<String> words = new ArrayList<>();
    	words.add(word);
    
    	if (word.length() == 5) return words;
    
   	 	for (char c : CHARS) {
    		words.addAll(generate(word + c));
   		}
    	return words;
    }
    
    public int solution(String word) {
		return generate("").indexOf(word);
	}
}