[ JavaScript ] 프로그래머스 level2 84512번 모음사전

모음사전 #84512 

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

프로그래머스

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

---

 

입출력 예wordresult

"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189

입출력 예 설명

입출력 예 #1

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2

"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3

"I"는 1563번째 단어입니다.

입출력 예 #4

"EIO"는 1189번째 단어입니다.

나의 풀이

function solution(word) {
  const aeiou = ["A", "E", "I", "O", "U"];
  const size = aeiou.length;
  let count = 0;

  let find = false; // word를 찾았는지 여부
  dfs("");

  function dfs(v) {
    if (v.length > 5 || find) return; // 기존 단어가 이미 5글자거나, 찾았으면 리턴
    if (word === v) find = true; // 찾으면 find를 true로
    if (!find) count++; // 아직 못찾았으면 카운트 증가

    for (let i = 0; i < size; i++) {
      dfs(v + aeiou[i]);
    }
  }
  return count;
}

• 깊이 우선 탐색으로 문제를 풀었다. 
• aeiou 배열에는 A,E,I,O,U 문자를 넣어주었고, 이 배열의 크기를 size 변수에 저장했다. 
• 탐색을 할 때마다 count를 증가시켜 몇번째 단어인지 알기 위해 count를 0으로 초기화한다. 
• 파라미터로 받은 word를 찾았으면 true, 아직 못찾았으면 false를 저장할 변수 find를 선언한다. 
• 처음에는 빈 문자열로 시작해 dfs 호출한다. 
• 만약 이미 만들어진 단어가 이미 5글자거나, find가 true이면 더 이상 탐색할 필요가 없으므로 리턴한다. 
• dfs의 파라미터로 넘어온 단어가 word와 같으면 find를 true로 바꿔준다. 
• 만약 아직 못찾았으면(find가 false이면) count를 증가시킨다.
• 넘어온 단어에 a,e,i,o,u 하나씩 붙이면서 탐색해야하므로, dfs 안에 size만큼 for문을 돌려 dfs 재귀함수를 호출한다. 

실행 시간도 비교적 짧게 걸린다! (word를 찾으면 더 이상 탐색을 안하기 때문에)

다른 풀이들 중에서 수학적으로 푼 풀이들도 많았는데, 완전 탐색 문제이기도 하고, 활용도가 더 높은 것은 dfs 방법인 것 같다.