프로그래머스 - 모음 사전(Level 2)

만들 수 있는 단어가 5^5개밖에 안되기 때문에 모든 단어를 다 순회해서 구한다

 

상태: 현재까지 만든 단어 (word)

종료조건: 단어의 길이가 5인 경우

점화식: (word)=[word] + (word+'A') + (word+'E') + (word+'I') + (word+'O') + (word+'U')

 

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

public class 모음_사전 {
   private static final char[] vowel="AEIOU".toCharArray();

   public List<String> generate(String word){ //재귀호출이 사전순으로 진행되게 된다
       List<String> words=new ArrayList<>();
       words.add(word); //현재까지 만든 단어 word를 리스트에 담기

       if(word.length()==5) //만든 단어의 길이가 5이면 리스트 리턴 후 종료
           return words;

       for(char ch:vowel){ //word 뒤에 하나씩 붙여가며 생성 후 리스트에 담기
           words.addAll(generate(word+ch)); //addAll() : 컬렉션 안의 객체들을 모두 리스트에 담는다
       }
       return words;
   }
    public int solution(String word) {

        return generate("").indexOf(word); //빈문자열을 넘겨주어 index는 ""가 0, "A"가 1이 된다.
        //따라서 word와 같은 단어의 인덱스 반환 가능
    }

}

 

1. char을 문자열과 연결하면 합쳐진 문자열이 반환된다

---

최적화된 코드

: 매 호출마다 리스트를 생성하지 않고 넘겨주기

 

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

public class 모음_사전 {
    private static final char[] vowel="AEIOU".toCharArray();

    public void generate(String word, List<String> words){ 

        words.add(word); 

        if(word.length()==5) 
            return;

        for(char ch:vowel){ 
            generate(word+ch,words);
        }
    }
    public int solution(String word) {
        List<String> words=new ArrayList<>();
        generate("",words);
        return words.indexOf(word); 
    }

}