04/22 알고리즘 공부(97) - 모음 사전

조건

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

알고리즘 예상

1. 깊이 우선 탐색을 이용해 각 자리의 알파벳이 해당하는 단어의 순번을 검색하는 방법이 있을 것 같다.
2. 수학적인 방법을 이용해 각 알파벳의 순번에 맞추어 1~5의 수를 부여한 후 순번을 찾는 방법도 있을 것 같다.

 

초기 코드

class Solution {
    fun solution(word: String): Int {
        var answer = 0
        return answer
    }
}

 

내 코드

import kotlin.math.pow
class Solution {
    fun solution(word: String): Int = word
            .split("")
            .map {
                when (it) {
                    "A" -> 1
                    "E" -> 2
                    "I" -> 3
                    "O" -> 4
                    "U" -> 5
                    else -> 0
                }
            }
            .filter { it != 0 }
            .run {
                var answer = 0
                forEachIndexed { idx, value ->
                    var temp = 0
                    repeat(5 - idx) {
                        temp += 5.0.pow(it).toInt()
                    }
                    temp *= (value - 1)
                    answer += temp + 1
                }
                answer
            }
}

 

다른 사람의 풀이

class Solution {
    val arr = arrayOf("A", "E", "I", "O", "U")
    val result = mutableListOf<String>()

    fun solution(word: String): Int {
        dfs("")
        result.forEachIndexed { idx, s ->
            if(s == word) return idx
        }
        return -1
    }

    fun dfs(str: String) {
        if(str.length > 5) return
        result.add(str)
        for(a in arr) {
            dfs(str + a)
        }
    }
}

 

개선점 또는 배운점

1. 최근 많이나오는 깊이 우선탐색을 이용한 풀이이다. 익숙해질 필요가 있다.