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

문제

 

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

프로그래머스

 

문제풀이

 

완전탐색으로 A부터 EEEEE까지 모든 경우의 수를 set에 저장한 뒤 A부터 탐색하여 풀었다.

 

미리 char형 배열을 선언하여 'A', 'E', 'I', 'O', 'U'를 저장한다.

DFS를 통해 완전탐색을 한다.

6자리 이상은 구할 필요가 없으므로 cnt > 4이면 return 한다.

(DFS를 실행하기 전에 미리 다음자리의 단어를 구하므로)

 

그 외의 경우는 현재 고른 알파벳의 개수+1, 현재 만든 단어 + 고른 알파벳을 DFS 인자로 넘긴다.

단어를 저장하는 set에도 저장한다.

 

코드

#include <string>
#include <vector>
#include <set>
using namespace std;

set<string>dict;
char alp[5] = { 'A','E','I','O','U' };

void DFS(int cnt, string word) {
    if (cnt > 4) return;
    for (int idx = 0; idx < 5; ++idx) {
        DFS(cnt + 1, word + alp[idx]);
        dict.insert(word + alp[idx]);
    }
}

int solution(string word) {
    int answer(0);
    DFS(0, "");
    for (auto iter = dict.begin(); iter != dict.end(); ++iter) {
        ++answer;
        if (*iter == word) return answer;
    }    
}