[프로그래머스] 모음 사전 - JS

모음 사전

❓ 문제설명

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

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

🚫 제한조건

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

✔ 입출력 예

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

💡 풀이

function solution(word) {
  // 내풀이
  // dfs로 사전을 만들고 순번을 리턴
  const vowels = ['A', 'E', 'I', 'O', 'U']

  let dic = []
  const dfs = (cur, len) => {
    if (len > vowels.length) {
      return
    }
    
    dic.push(cur)

    vowels.forEach(d => {
      dfs(cur + d, len + 1)
    })
  }

  dfs('', 0)

  return dic.indexOf(word)

  // 다른사람 풀이
  // 수식을 활용한 풀이
  return word.split('').reduce((a,b,i) => a + ('AEIOU'.indexOf(b)) * (5**(5 - i) - 1) / 4 + 1, 0)
}

📝 해설

깊이 우선 탐색을 사용하여 dic 배열에 사전을 먼저 정의한다. A 부터 시작해서 해당 알파벳을 먼저 dic 배열에 추가하고 이후에 각 모음을 붙여서 (AA, AE, AI, AO, AU) 다시 길이가 2인 dfs 를 실행하면 AA 관련된 과정이 먼저 실행(스택) 되고 이 후 dfs('AAA', 3) 이 실행된다. 전체 과정을 보자면 dfs('', 0) > dfs('A', 1) > dfs('AA', 2) > dfs('AAA', 3) > dfs('AAAA', 4) > dfs('AAAAA', 5) > dfs('AAAAE', 5) > ... > dfs('UUUUU', 5) 순으로 실행된다. 이 후 dic 에서 찾고자 하는 단어를 찾아 반환하였다.

 

다른 사람 풀이를 보면 각 자리의 알파벳에 따라 공식을 적용하여 푸는 방법도 있다. 어떤 식으로 공식을 만든 것 인지는 아직 잘 모르겠다...

📚 참고자료

- https://kimby.tistory.com/48 (Array 메소드)