[자바스크립트, js] 프로그래머스 모음사전

안녕하세요,

 

오늘은 난이도 2의 '모음사전'을 가져왔습니다!! 

 

풀었던 저의 주관적인 풀이를 공유하고자 합니다!

---

 문제 설명

사전에 알파벳 모음 '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

---

우선 A -> AA -> AAA -> AAAA -> AAAAA 까지 총 5개까지 등장하며 그 다음은 순서대로 A E I O U가 등장할 것입니다. 그렇죠 이것은 DFS를 사용해서 풀면 풀릴 것 같습니다.

 

A를 하나씩 추가하면서 result를 하나씩 증가시켜주고, AAAAE를 만날 당시의 result 값을 리턴해주면 될 것 같습니다. 

 

시작은 빈 문자열로 시작하며, 사전에 등장하는 리스트를 for문을 통해 하나씩 넣어주는 방식으로 진행하였습니다.

function solution(word) {
  var answer = 0;
  let count = 0
  const arr = ['A', 'E', 'I', 'O', 'U']
  
  const dfs = (str) => {
      if(str === word){
          count = answer
      }
      else if (str.length <= 4){
          for(let i =0; i<arr.length; i++){
              answer++
              dfs(str+arr[i])
          }
      }
  }
  
  dfs('')
  return count;
}

dfs의 조건은, str 즉 문자열의 길이가 5개까지만 동작해야 합니다. 그렇기에 if(str.length <= 4)를 해준 것입니다. 그럼 str길이가 4일때, 즉 AAAA의 상황에서 A를 하나 더 넣은 5개 이후부턴 동작하지 않을 것입니다.

 

그렇게 재귀를 돌리다 보면 언젠간 찾아야하는 값이 등장할 것이고, 그 조건, word를 만나면 count에 answer 값을 넣어주면 됩니다.

 

여기서!!!!! 한가지 생각을 해야하는데요, count에 원하는 값인 6이 들어갔어도 재귀는 사전의 끝까지 돌게될 것입니다. 왜냐? 제약 조건이 없기 때문이죠.!!

 

실제로 위에 실행 시간은 

이전 소스 실행 시간

이 실행시간을 줄이기 위해서 count값에 원하는 값이 들어갔다면 재귀를 실행하지 않게 하려고 합니다. 그 조건!!! count === 0을 넣어주면 됩니다.

function solution(word) {
    var answer = 0;
    let count = 0
    const arr = ['A', 'E', 'I', 'O', 'U']

    const dfs = (str) => {
        if (str === word) {
            count = answer
        }
        else if (count === 0 && str.length <= 4) {
            for (let i = 0; i < arr.length; i++) {
                answer++
                dfs(str + arr[i])
            }
        }
    }

    dfs('')
    return count;
}

위처럼 count 조건을 넣어주고 실행해 본다면

소스에 조건문 추가

위 조건을 추가한 후에는 전반전으로 전 소스에 비해 실행시간이 좀 많이 줄어든 것을 볼 수 있습니다. 불필요한 실행을 줄여 효율성을 높여라!! 항상 기억하고 개발해야 겠습니다 ㅎㅎ..

 

여기까지.. 모음사전 문제였습니다!!

 

다른 풀이들도 한번 방문해주세요~

 

한솔방울 깃허브

 

이상 감사합니다!!