[프로그래머스/C++/JS] 모음 사전

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

1. 문제

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

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

2. 제한사항

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

3. 풀이

다양한 방법이 있다.
가장 무식하고 단순하게 풀었다.

• A, E, I, O, U로 만들 수 있는 모든 경우의 수를 구하고 정렬을 한 다음에 몇 번째 인지 찾았다.
• 단어가 5개 글자 미만이기 때문에 5! X 4! X 3! X 2! X 1!가지 경우의 수가 있기 때문에 충분히 가능할 것 같았다.
• 1부터 5까지 반복문을 돌며 dfs(word, target)를 실행하였다.
• dfs는 target 길이의 문자열이 생길 때까지 word에 A, E, I, O, U 중 하나를 추가한다.
• word의 길이가 target과 같아지면 해당 문자열을 문자열 배열에 저장한다.
• 모든 동작이 끝난 후 문자열 배열을 정렬한다.
• 원하는 문자가 사전에서 몇 번째인지 찾는다.

4. 처음 코드와 달라진 점

• 배열의 인덱스는 0부터 시작해서 나온 답에서 1을 더해주어야 원하는 답이 나온다.
• A, E, I, O, U 문자 배열 초기화 작업을 v.push_back()에서 선언하면서 바로 초기화 하는 걸로 변경했다.
• dfs(string word, int count, int target)에서 문자 길이로 count 변수를 대신하는 걸로 변경했다.

5. 코드

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

using namespace std;

vector<string> v;
vector<char> alphabet = {'A', 'E', 'I', 'O', 'U'};

void dfs(int target, string word="") {
    if (word.size() == target) {
        v.push_back(word);
    }
    else {
        for (char c : alphabet) {
            word += c;
            
            dfs(target, word);
            
            word.pop_back();
        }
    }
}

int solution(string word) {
    int answer = 0;

    for (int i = 1; i <= 5; ++i) {
        dfs(i);
    }
    
    sort(v.begin(), v.end());
    
    for (int i = 0; i < v.size(); ++i) {
        if (word == v[i]) {
            answer = i + 1;
            break;
        }
    }
    return answer;
}

6. 코드(JS)

function solution(word) {
    const vowels = ['A', 'E', 'I', 'O', 'U'];
    let result = [];
    
    const dfs = (len, res) => {
        if (res.length === len) {
            result = [...result, res];
        } else {
            for (let i = 0; i < 5; i++) {
                dfs(len, res + vowels[i]);
            }
        }
    }
    for (let i = 1; i <= 5; i++) {
        dfs(i, '');
    }

    return result.sort().findIndex(res => res === word) + 1;
}