728x90
완전탐색
A, E, I, O, U 으로만 이루어진 단어 사전이 있다. 이 사전에 수록된 단어의 최대 길이는 5일때,
특정 단어가 주어지면, 이 단어의 순서를 반환하는 문제
<사전 예시>
"A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"
접근방법
어차피 한번에 단어 한개만 주어져서 저장해두고 쓰는 것도 불필요해서, 그냥 매번 순서를 셌다..(이게맞나 암튼 완전탐색임)
DFS처럼 순서대로 단어를 체크했고, 이 문제에서는 의외로(?) 관건이 언제 재귀함수를 종료할 것인가 였다.
1. cnt 증가 (단어 순서)
2. 찾아야할 단어의 순서인지 확인 -> 맞으면 answer = cnt 담고 함수 종료
3. 단어의 길이가 5이면 함수 종료 (이래야 단어의 길이가 6인 것 까지 순서를 세지 않음)
4. 현 단어에 모음 순서대로 하나씩 붙이기 (dfs 호출)
오답노트
- 처음 dfs를 호출할 때 '현 단어(word)'에 빈 문자열을 보낼 거기 때문에 cnt는 그것까지 포함하고 있어서, 마지막에 answer 반환할 때 1빼줘야한다.
소스코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int cnt = 0;
int answer = 0;
char vowels[5] = {'A', 'E', 'I', 'O', 'U'};
void dfs(string word, string goal){
cnt++;
if(word == goal){
answer = cnt;
return;
}
if(word.size() == 5)
return;
for(int i = 0 ; i < 5 ; i++){
dfs(word+vowels[i], goal);
}
}
int solution(string word) {
dfs("", word);
return answer-1;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[프로그래머스] 단속카메라 (C++) (0) | 2024.11.07 |
---|---|
[프로그래머스] 구명보트 (C++) (0) | 2024.11.06 |
[프로그래머스] 주식가격 (C++) (3) | 2024.11.04 |
[프로그래머스] 전력망을 둘로 나누기 (C++) (0) | 2024.11.04 |
[프로그래머스] 폰켓몬 (C++) (0) | 2024.10.31 |