프로그래머스 - Lv.2 모음사전(백트래킹) JS

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

 

해당 문제는 모음 A,E,I,O,U 를 조합하여 1~5 길이의 단어를 만들어 각각에 순서를 붙이고, 특정 문자열을 제시할 때 해당 문자열이 몇 번째 위치하는가에 대한 문제다.

 

먼저 A,E,I,O,U 를 조합하여 만들 수 있는 1~5가지의 문자열의 갯수는 3905(5^5 + 5^4 + 5^3 + 5^2 + 5^1)이기 때문에, 완전 탐색을 수행해도 높은 시간 복잡도가 우려되지는 않았다.

허나 이미 답에 맞는 문자열을 찾았음에도, 구태여 모든 탐색을 진행하는 것은 불필요하기에 내가 만든 문자열과 문제에서 제시된 문자열이 같다면 중지되도록 구현했다.

 

소스 코드

function solution(word) {
  const vowels = ['A','E','I','O','U']
  let compare = '' // 만들어지는 문자열을 담는 변수
  let result = 0 // 결괏값을 담는 변수 => 밑에 반복문이 진행될수록 값 증가
  let toggle = false // 결괏값을 찾았을 때 모든 반복문을 탈출할 수 있도록 임시로 만든 변수
  const backTracking = () => {
    if(compare.length === 5) return
    else {
      for(let i = 0 ; i < 5 ; i ++) {
      	// toggle = true 일 경우 모든 반복문을 탈출할 수 있도록 함
        if(toggle) return
        compare += vowels[i]
        result ++
        // # 만들어진 문자열이 문제에서 제시된 문자열과 같다면 toggle = true로 설정
        if(compare === word) toggle = true 
        backTracking()
        compare = compare.slice(0, compare.length - 1)
      }
    }
  }

  backTracking()
  return result
}

console.log(solution('AAE'))