▶ 문제출처
https://school.programmers.co.kr/learn/courses/30/lessons/84512
▶ 문제 설명: 완전탐색
영어 알파벳 모음으로만 형성된 word 문자열이 주어진다. 모음으로만 구성된 문자열을 사전순으로 만들어 word 문자열과 같아질때 사전순으로 만든 문자열이 몇 번째 단어인지 구하는 문제이다.
▶ 로직:
1. 재귀함수를 이용해 vowels 배열에 있는 모음을 사전순으로 만들어 wordAnswer단어를 형성할 것이다.
2. level인 lv이 wordAnswer의 인덱스가 되고, branch의 원소인 x가 wordAnswer에 할당할 vowels의 인덱스가 된다.
level에서 단어를 하나 만들때마다 answer가 카운팅된다.
3. 만일 wordAnswer과 word_cp (word를 복사) 가 같으면 가지치기를 위해 bool형 endRecursion 을 true로 만들고 가지치기로 recursion 함수를 끝낸다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int answer;
const char* word_cp;
char wordAnswer[6]; // 최대 5글자 만들 수 있음. 마지막 하나는 널 포함시킴.
bool endRecursion = false;
char vowels[5] = { 'A','E','I','O','U' }; // 단어를 만들기 위해 주어진 모음
void recursion(int lv) {
if (!strcmp(word_cp,wordAnswer)) { // 문자열이 같으면 0으로 반환.
endRecursion = true; // word_cp와 재귀함수로 만들어진 wordAnswer 문자열이 동일하면 Recursion함수를 끝내기 위한 bool endRecursion을 true로 설정.(가지치기 용도)
}
if (lv ==sizeof(vowels)) {
return;
}
for (int x = 0; x < sizeof(vowels); ++x) {
if (endRecursion)return; // 가지치기
wordAnswer[lv] = vowels[x]; // level, branch(x)에 따라 모음으로 만들어진 문자열 형성. 'A','AA','AAA','AAAA', 'AAAAA' 'AAAAB', 'AAAAC' 순으로 진행.
answer++; // answer값 카운팅.
recursion(lv + 1);
if (endRecursion)return;
wordAnswer[lv] = NULL;
}
return;
}
// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
int solution(const char* word) {
word_cp = word; // 전역변수인 word_cp 에 word 복사
recursion(0);
return answer;
}
int main(void) {
solution("EIO");
}