[프로그래머스] 위클리 챌린지 (5주차)

 

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

코딩테스트 연습 - 5주차

#include <string>
#include <vector>
#define MAX 5
using namespace std;
char aeiou[MAX]={'A','E','I','O','U'};
char selected[MAX];
int answer;
int order=0;

void dfs(int cnt, string s, string word){
    if (s==word){
        answer=order;
        return;
    }
    if (cnt==5){
        return;
    }
    for (int i=0; i<MAX; i++){
        selected[cnt]=aeiou[i];
        s+=selected[cnt];
        order++;
        dfs(cnt+1,s,word);
        s.pop_back();
    }
}

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

DFS, 중복순열을 이용해서 풀었다.

재귀에 약하기 때문에 순열, 조합에 대한 DFS 지식을 충분히 익혀야겠다.

 

selected 배열에 선택된 애들을 넣어주고(A,E,I,O,U 순서대로), 순서를 나타내는 Order 변수를 1 증가시킨다.

DFS를 재귀적으로 수행하고, DFS 가 다 돌려지면 선택된 애들을 빼준다.

cnt가 5(총 글자 수가 5)이거나 word와 동일할 때 탐색을 멈춘다.