[프로그래머스] 모음사전 (Lv 2) - javascript / dfs

📝 문제

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
 

• 제한사항
  • word의 길이는 1 이상 5 이하입니다.
  • word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
     

🤔 나의 풀이

규칙을 찾아 푸는 방법도 있지만, 출제 의도에 맞는 풀이 같지는 않았다.
우리가 계산하기 힘들기 때문에 컴퓨터에게 맡기는 것이기 때문에... 로직을 만들고 컴퓨터가 찾아내는 풀이를 찾았다.
 

function solution(word) {
    const words = ['A', 'E', 'I', 'O', 'U'];
    const dict = [];

    function getDict(word, dept) {

        if(dept === 6) return;
        dict.push(word);

        for(let nextWord of words) {
            getDict(word + nextWord, dept + 1);
        }
    }

    words.forEach((word) => getDict(word, 1));

    return dict.indexOf(word) + 1;
}

 
아래 참고에 있는 블로그를 참고했다.
재귀 함수를 이용해 모든 경우로 배열을 만들고 인덱스를 찾는 방식이다.
시간은 3초대로 다소 느리다.

 

🔑 모범 풀이

function solution(word) {

   let answer = [];
    
    function dfs(w) {
        if(w.length > 5) return;
        answer.push(w);
        for(let char of "AEIOU") {
            dfs(w+char);
        }
    }
    
    dfs("");
    return answer.indexOf(word);
}

 
위 풀이와 방식은 같지만, 훨씬 간결하다.
answer의 첫 번째 값으로 ''이 들어가기 때문에 word의 인덱스에 1을 더해주지 않아도 된다.
 

문자열에 문자열을 더해서 경우의 수를 만들어나가는 과정이 재귀 하나로 쉬워진다.
재귀를 잘 다루게 되도록 많이 연습해야겠다.

 

🤷‍♀️ 문자열이 만들어질 때마다 카운트를 세다가, word와 비교해서 같으면 cnt를 반환하는 방식은 왜 안될까?

 재귀로 함수가 깊게 호출되다가 word를 찾았을 때, return cnt 하면 빠져나오는건 해당 깊이의 함수일 뿐이다.

빠져나오며 해당 cnt가 반환되는 것이 아니라 그 윗 깊이의 함수가 마저 실행된다는 뜻이다.

그러니 위의 방법으로 하는 것이 더 쉽다.
 

• 정확도 테스트 결과

 

---

참고

velog.io/@cjh951114

programmers.co.kr/learn/courses/