[프로그래머스 - Java] 5주차

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

코딩테스트 연습 - 5주차

 

풀이

사전의 단어 순서대로 재귀를 이용해서 단어를 생성하면서 dfs 방식으로 문제를 해결했습니다.

재귀를 이용하면 재귀의 호출 횟수와 해당 문자열이 사전에 나오는 순서가 동일하기 때문에 쉽게 문제 해결이 가능합니다.

 

1. 단어가 하나도 추가되지 않은 상태인 dfs(0, "", word)를 호출하는 것으로 재귀를 시작합니다.
2. dfs에서는 받아온 now 문자열에 차례로 'A', 'E', 'I', 'O', 'U'를 붙이면서 재귀를 호출합니다.
3. 재귀를 호출할 때마다 answer값을 1씩 증가시켜줍니다. (재귀 호출 횟수가 그 문자열이 사전에 나오는 순서이기 때문)
4. 재귀를 반복하면서 now문자열과 주어진 word문자열이 동일해지는 경우 true를 반환합니다.
5. 동일한 문자열을 찾지못하고 길이 5에 도달하는 경우엔 false를 반환합니다.
6. 재귀에서 돌아왔을 때 true값이 반환되었다면 동일하게 true를 반환하면서 재귀를 종료해가고, 그렇지 않은 경우엔 계속 수행해 나갑니다.

 

class Solution {
    int answer = 0;
    public int solution(String word) {
        //빈 문자부터 시작
        dfs(0, "", word);
        return answer;
    }
    
    public boolean dfs(int cnt, String now, String word){
        //같은 단어 찾으면 true 반환
        if(word.equals(now))
            return true; 
        //같은 단어 찾기 전 길이 5 -> false 반환
        if(cnt == 5)
            return false;
        
        //A,E,I,O,U 순서로 하나씩 붙이면서 재귀 호출
        answer++;
        if(dfs(cnt+1, now+'A', word))
            return true;
        answer++;
        if(dfs(cnt+1, now+'E', word))
            return true;
        answer++;
        if(dfs(cnt+1, now+'I', word))
            return true;
        answer++;
        if(dfs(cnt+1, now+'O', word))
            return true;
        answer++;
        if(dfs(cnt+1, now+'U', word))
            return true;
        
        
        
        return false;
    }
}