프로그래머스 모음사전 - C++

문제

---

프로그래머스

 

 

풀이

---

 

이 문제는 2가지 풀이가 존재한다.

첫번째는 DFS로 푸는 방법이고, 두번째는 수식 계산을 통해 푸는 방법이다.

 

DFS로 푸는 방법

DFS로 푸는 방법은 깊이를 하나씩 늘려가며 사전을 전부 만드는 것이다.

우선순위를 A, E, I, O, U로 두어 우선순위가 가장 높은 곳부터 깊이 우선 탐색을 하며 된다. ▼

 

A부터 시작해서, 다음 깊이에서 우선도가 높은 A부터 쭉 탐색해나가며 사전을 전부 만들고 검증하면 된다.

 

수식으로 푸는 방법

다음으로는 수식으로 푸는 방법이다.

필자는 이 방법으로 먼저 풀었다.

 

A, E, I, O, U로 만들 수 있는 각 자리 별 모든 경우의 수를 구하면 다음과 같다. ▼

 

4자리일 때는 780, 3자리일 때는 155, 2자리일 때는 30, 1자리일 때는 5가지가 나온다.

각 경우의 수를 이전 단어에 따라 몇가지가 올 수 있는지 곱하여 더해주면 쉽게 구할 수 있다.

 

"I"라는 문자열이 들어왔다고 하면, I 앞에 A와 E가 있기에 2 * 780에 I 자체가 3번째 단어이기에 3을 더해주면 1563번째라는 값이 바로 나오게 된다. ▼

 

 

C++ 코드 - DFS 풀이

---

#include <string>
#include <vector>

using namespace std;

vector<string> dictionary;
string vowels[5] = {"A", "E", "I", "O", "U"};

void dfs(string str, int len) {
    dictionary.push_back(str);
    if (len == 5) return;
    
    for (int i = 0; i < 5; i++) {
        dfs(str + vowels[i], len + 1);
    }
}

int solution(string word) {
    int answer = 0;
    
    dfs("", 0);
    
    while(true) {
        if (dictionary[answer] == word) {
            return answer;
        }
        answer++;
    }

    return answer;
}

 

 

C++ 코드 - 수식 풀이

---

#include <string>
#include <vector>

using namespace std;

int getIndex(char c) {
    if (c == 'A') return 1;
    else if (c == 'E') return 2;
    else if (c == 'I') return 3;
    else if (c == 'O') return 4;
    else if (c == 'U') return 5;
}

int getCntByDepth(int depth) {
    if (depth == 0) return 780;
    else if (depth == 1) return 155;
    else if (depth == 2) return 30;
    else if (depth == 3) return 5;
    else if (depth == 4) return 0;
}

int dfs(int depth, string word) {
    int ret = 0;
    int index = getIndex(word[depth]);
    
    ret += (index - 1) * getCntByDepth(depth);
    ret += index;
    if (depth >= word.size()) {
        return 0;
    } else {
        ret += dfs(depth + 1, word);
    }
    return ret;
}

int solution(string word) {
    int answer = 0;
    
    answer = dfs(0, word);
    return answer;
}