[Java / Kotlin] 99 클럽 코딩 테스트 스터디 미들러 16일차 - 모음 사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=java

프로그래머스

 

[문제]

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

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

 

[제한 사항]

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

[풀이]

완전 탐색 문제입니다.

AEIOU를 이어 붙여서 만들 수 있는 모든 단어를 리스트에 정리해야 합니다.

이때 중첩 for문이 아니라 재귀를 통해 처리해 줍니다.

그리고 정리된 리스트에서 찾는 단어의 index 값 + 1을 반환해 주면 됩니다.

 

아래는 자바 코드입니다.

public static List<String> result = new ArrayList<>();
public static List<Character> vowels = List.of('A', 'E', 'I', 'O', 'U');

public static void check(String currentWord) {
    if (currentWord.length() <= 5) {
        if (!currentWord.isEmpty()) {
            result.add(currentWord);
        }
        for (Character vowel : vowels) {
            check(currentWord + vowel);
        }
    }
}

public static int solution(String word) {
    check("");
    return result.indexOf(word) + 1;
}

check 함수가 재귀적으로 호출되며 구성 가능한 단어들을 모두 List에 정리합니다.

인자로 들어오는 word가 문제에서 주어진 5글자 이하이고, ""가 아니라면 리스트에 저장하고 방금 넣는 단어에 다시 Char를 더해 연산을 진행해 줍니다.

 

아래는 코틀린 코드입니다.

fun solutionVowels(word: String): Int {
    val vowels = listOf('A', 'E', 'I', 'O', 'U')
    val result = mutableListOf<String>()

    fun backtrack(currentWord: String) {
        if (currentWord.length <= 5) {
            if (currentWord.isNotEmpty()) {
                result.add(currentWord)
            }
            for (vowel in vowels) {
                backtrack(currentWord + vowel)
            }
        }
    }
    backtrack("")

    return result.indexOf(word) + 1
}