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

모음사전

 

고려할 점

규칙이 뭔지 생각하는 게 유일한 포인트

반복문만으로도 만들  수 있을 것 같지만 복잡함

 

출제 의도가 있을거란 생각에 그려보니

트리구조와 동일하다는 특징!

 

 

내가 만든 코드

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

string origin = "AEIOU";
string strAnswer = "";
int count = 0;
int num = 0;

void dfs(int length, string str){
    if(length >= 5)
        return;

    for(int i = 0; i < 5; i++){
        str += origin[i];
        count++;
        if(str == strAnswer){ num = count; }
        dfs(length + 1, str);
        str.erase(str.end() - 1);
    }
}

int solution(string word) {
    string str = "";
    strAnswer = word;
    dfs(0, str);
    return num;
}

 

 

코드 설명

1. 트리와 동일하니 dfs로 풀어야겠다

2. 근데 간선 정보가 없네. 어디서 멈춰야 하지?

3. length 변수를 만들어 5번만 돌게 만들자

 

재귀함수를 만들 때면 생각하는 게

리턴값, 매개변수 포인터 사용이 어렵다.

결국 전역변수로 퉁치지만 코테에서나 가능한 방법이라는 생각이 든다

 

본받을 만한 코드 - 1

781, 156, 31, 6, 1이라는 숫자를 사용하는 방법이 있음

도대체 뭔지 모르겠어서 인터넷 좀 찾아봤더니

 

총 5자리의 알파벳에서 생각하는데

1의 자리 A가 E가 되는데 1이 증가한다.

2의 자리 A가 E가 되는데 6이 증가한다.

....

5의 자리 A가 E가 되는데 781이 증가한다.

라는 경우의 수를 계산해 놓고 적용하는 방식이었다.

 

경우의 수를 미리 계산하고 값만 적용시키는 방법을 사용한 사람이 꽤 많았다.

 

심지어 string.rfind로 뒤에서부터 계산하면서 

(int)( 781 / 5의 배수 )라는 방식으로 만든 코드는 놀라웠다.

 

 

본받을 만한 코드 - 2

비슷한 방법이기는 한데

모든 경우의 수를 만들어 배열에 넣고 정렬 

정렬 후 find 하는 방법이 있음

 

가독성은 높았다.