[프로그래머스] LEVEL2 모음사전 JAVA

모음사전

문제링크

풀이

dfs or 수학

1. list에 A, E, I, O, U로 만든 최대 길이가 5인 단어들을 모두 넣는다.

2. dfs를 활용해서 cnt로 현재 단어의 길이를 파악하고, cur로 현재까지 조합된 단어들을 저장하고 있다.

3. 기본적인 원리는 중복 순열과 동일하지만, 특정 n개를 뽑는게 아니기에 모든 길이의 단어들을 다 저장한다.

4. 코드 1에서, list를 정렬하는 과정과 ""단어를 빼주는 과정을 추가했었는데, dfs가 순서대로 탐색하기에 이 과정을 필요없었고, 또 list.indexOf라는 함수를 이용하면 바로 쉽게 해당 단어의 위치를 알 수 있었다. 이를 통해 더 간결하고 실행 속도가 빠른 코드를 생성할 수 있었다.

코드 1: Time: 18.58 ms, Memory: 71.8 MB
코드 2: Time: 15.11 ms, Memory: 83.4 MB

코드

import java.util.*;
class Solution {
    char[] inputs = {'A', 'E', 'I', 'O', 'U'};
    List<String> list = new ArrayList<>();
    public int solution(String word) {
        int answer = 0;

        dfs(0, "");
        Collections.sort(list);
        
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(word)) {
                answer = i + 1;
                break;
            }
        }
        return answer;
    }
    
    public void dfs(int cnt, String cur) {

        if (!cur.equals(""))
            list.add(cur);
        
        if (cnt == 5) {
            return;
        } 
        
        for (int i = 0; i < 5; i++) {
            dfs(cnt + 1, cur + inputs[i]);
        }
    }
}

코드 2 (더 효육적으로)

import java.util.*;
class Solution {
    char[] inputs = {'A', 'E', 'I', 'O', 'U'};
    List<String> list = new ArrayList<>();
    public int solution(String word) {
        int answer = 0;

        dfs(0, "");
        
        return list.indexOf(word);
    }
    
    public void dfs(int cnt, String cur) {

        list.add(cur);
        
        if (cnt == 5) {
            return;
        } 
        
        for (int i = 0; i < 5; i++) {
            dfs(cnt + 1, cur + inputs[i]);
        }
    }
}