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

완전탐색을 이용하면 간단하게 풀리는 문제이다. 

 

#접근방법

 

먼저 전달받은 문자열이 사전의 몇번째 위치인지 확인하려면 사전을 미리 만들어야한다. 

 

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다.

 

위의 조건을 보면 알파벳 모음은 5개밖에 없고 길이도 5이하라면 완전탐색으로 사전을 만드는데 충분한 시간을 가지고 있다는 것이다.

 

 

A : 1

AA : 2

AAA : 3

AAAA : 4

AAAAA : 5 

AAAAE  : 6

 

위의 순서를 보면 DFS가 살짝 보인다.

뭔가 문자열 길이가 5일때까지 A를 뒤에다가 붙여주고 길이가 5가 된다면 맨끝 알파벳을 E로 바꿔주고 그다음에는 I가 될거고 ... 대충 느낌이 올것이다. 

 

즉, DFS 방식으로 적용해서 LEVEL이 5일 때까지 쭉 내려가는 것이다. 

그 후에 LEVEL 5가 된다면 LEVEL 4로 돌아가서 그다음 알파벳인 E를 끝으로 교체하고 다시 LEVEL 5로 가면되는것이다. 

 

Unordered_map 자료구조를 활용하여 재귀를 호출하기 전마다 만들어진 문자열을 키값으로 가지며 전역변수로 생성한 order 값을 저장한 후 order값을 하나 증가시켜준다.  

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int order=1; 
char arr[5]={'A', 'E', 'I', 'O', 'U'}; 
unordered_map<string, int> m; 
void dfs(int level, string s){
    if(level==5)return; 
    for(int i=0; i<5; i++){
        string temp = s; 
        temp+=arr[i]; 
        m[temp]=order++;
        dfs(level+1, temp); 
    }
}

int solution(string word) {
    dfs(0, ""); 
    return m[word]; 
}

 

코딩테스트 연습 - 모음사전