[Programmers] 모음 사전 (Java, Kotlin)

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

코딩테스트 연습 - 5주차

문제

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 반환하면 됩니다.

 

접근 아이디어

1. AEIOU 중에서 A를 하나씩 늘려나가고 마지막에서는 AEIOU 순으로 진행하는 것을 생각해보니 DFS 알고리즘을 적용해보면 좋을 것 같다고 생각했습니다.

2. DFS 알고리즘을 적용하면서 멤버 변수인 count를 이용하여 몇 번째 단어인지 카운팅하였습니다.

3. 입력값으로 들어온 word와 매칭되는 다음 문자열이 있다면 isStop을 true로 바꾸어 DFS 알고리즘을 모두 종료시켜 성능을 개선하였습니다.

 

조심해야할 점

5글자인 상태에서 DFS 함수를 한 번 더 타고들어가야 종료되기 때문에, 다음 길이가 6미만인 지점에서만 count 변수에 1을 추가했습니다.

 

 

- Java

class Solution {

    char[] aeiou = {'A','E','I','O','U'};
    int count = 0;
    boolean isStop = false;
    
    public int solution(String word) {
        dfs(0, "", word);
        return count;
    }
    
    public void dfs(int depth, String next, String target) {
        if (depth == 6) return;

        if (next.equals(target)) {
            isStop = true;
            return;
        }

        for (int i=0; i<5; i++) {
            if (isStop) return;

            if(depth + 1 < 6) count++;
            dfs(depth + 1, next + aeiou[i], target);
        }
    }
}

 

 

- Kotlin

class Solution {

    val aeiou = charArrayOf('A','E','I','O','U')
    var count = 0
    var isStop = false

    fun solution(word: String): Int {
        dfs(0, "", word)
        return count
    }

    fun dfs(depth: Int, next: String, target: String) {
        if(depth == 6) return

        if(next == target) {
            isStop = true
            return
        }

        for (each in aeiou) {
            if(isStop) return
            
            if(depth + 1 < 6) count++
            dfs(depth + 1, next.plus(each), target)
        }
    }
}

 

 

좌(Java 채점 결과), 우(Kotlin 채점 결과)