문제 푼 날짜 : 2021-09-10
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/84512
아래의 생각대로 코드를 구현하였다.
- 1~5자리로 만들 수 있는 모든 단어를 구해준다. (백트래킹)
- 구해진 단어들을 오름차순으로 정렬해준다.
- 찾고싶은 단어의 위치를 find함수를 통해 찾아주고, 그 위치를 return해준다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string alpha = "AEIOU";
void makeWords(string candid, int len, vector<string> &v) {
if (candid.length() == len) {
v.push_back(candid);
return;
}
for (char ch : alpha) {
makeWords(candid + ch, len, v);
}
}
int solution(string word) {
int answer = 0;
vector<string> v;
for (int i = 1; i <= 5; i++) {
makeWords("", i, v);
}
sort(v.begin(), v.end());
auto it = find(v.begin(), v.end(), word);
answer = it - v.begin() + 1;
return answer;
}
백트래킹 문제 더 풀어보기