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

문제

프로그래머스

주어진 단어가 사전 순으로 몇 번째인지 구하는 문제였다.

 

나의 풀이 전략

DFS로 푼다.

 

상세

1. DFS 함수의 이름은 makeCombination()이다.

우리가 조합한 단어는 comb, 문제에서 주어진 단어는 dest, 재귀깊이는 depth로 설정한다.

void makeCombination(string comb, string dest, int depth) // DFS
{

}

 

2. 우리가 이용할 모음은 정해져있다. 상수 문자 배열로 고정해주자.

// 전역
const char vowSet[5] = {'A', 'E', 'I', 'O', 'U'};

 

3. vowSet을 일순하며 comb에 모음을 넣으면서 count를 한다.

comb가 dest와 일치하면 count를 answer로 넣는다.

그리고 다음 재귀로 진입한다.

재귀탈출 후 다음 comb를 위해 마지막 글자를 빼준다.

int count = 0;
int answer = 0;

void makeCombination(string comb, string dest, int depth) // DFS
{
    for(int i = 0; i < 5; ++i)
    {
        comb.push_back(vowSet[i]); count++;
        if(comb == dest) answer = count;
        makeCombination(comb, dest, depth + 1);
        comb.pop_back();
    }
}

 

4. 기저조건을 설정한다.

void makeCombination(string comb, string dest, int depth) // DFS
{
    if(depth == 5) return;

    for(int i = 0; i < 5; ++i)
    {
        comb.push_back(vowSet[i]); count++;
        if(comb == dest) answer = count;
        makeCombination(comb, dest, depth + 1);
        comb.pop_back();
    }
}

 

전체 소스코드

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

const char vowSet[5] = {'A', 'E', 'I', 'O', 'U'};

int count = 0;
int answer = 0;

void makeCombination(string comb, string dest, int depth) // DFS
{
    if(depth == 5) return;

    for(int i = 0; i < 5; ++i)
    {
        comb.push_back(vowSet[i]); count++;
        if(comb == dest) answer = count;
        makeCombination(comb, dest, depth + 1);
        comb.pop_back();
    }
}

int solution(string word)
{
    makeCombination("", word, 0);

    return answer;
}