[Programmers] 84512번 - 모음사전 [Java][C++]

문제 링크

---

1. 아이디어

알파벳 모음 A, E, I, O, U만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있는 사전에서 word가 몇 번째 단어인지 return하는 문제다. 모음이 5가지이고 단어의 길이도 최대 5라서 모든 가능한 단어를 미리 구해 배열에 담은 후 사전 순으로 정렬하고 몇 번째에 위치하는지 찾는 방식을 활용했다.

---

2. 복잡도

시간복잡도	공간복잡도
$O(K^L \cdot L\log(K^L))$	$O(K^L \cdot L)$

$K$ = 모음 개수(5), $L$ = word 최대 길이(5)

---

3. 코드

풀이 [Java][C++]

중복 순열을 활용해 길이 1 부터 5까지 가능한 단어 조합을 구해서 리스트에 넣은 후 정렬을 수행하고 리스트를 순회하며 단어를 발견하면 return을 해줬다.

import java.util.*;

class Solution {

    static List<String> list = new ArrayList<>();
    static char[] arr = {'A', 'E', 'I', 'O', 'U'};
    static char[] sel = new char[5];

    public int solution(String word) {
        for (int i = 1; i <= 5; i++) {
            dfs(0, i);
        }
        list.sort(Comparator.naturalOrder());

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(word)) {
                return i + 1;
            }
        }

        return 0;
    }

    static void dfs(int idx, int len) {
        if (idx == len) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < len; i++) {
                sb.append(sel[i]);
            }
            list.add(sb.toString());
            return;
        }

        for (char c : arr) {
            sel[idx] = c;
            dfs(idx + 1, len);
        }
    }
}

중복 순열을 활용해 길이 1 부터 5까지 가능한 단어 조합을 구해서 벡터에 넣은 후 정렬을 수행하고 벡터를 순회하며 단어를 발견하면 return을 해줬다.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

vector<string> v;
string arr = "AEIOU";
string sel(5, ' ');

void dfs(int idx, int len) {
    if (idx == len) {
        v.push_back(sel.substr(0, len));
        return;
    }

    for (char c : arr) {
        sel[idx] = c;
        dfs(idx + 1, len);
    }
}

int solution(string word) {
    for (int i = 1; i <= 5; i++) {
        dfs(0, i);
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        if (v[i] == word) {
            return i + 1;
        }
    }

    return 0;
}

---