A E I O U를 기반으로 한 문자열들은 A, AA, AAA, AAAA, AAAAA, AAAE 순서로 증가한다.
이 때, 주어진 문자열이 해당 문자열들 중 몇번 째에 위치하는지 알아내면 되는 문제이다.
문제를 해결하기 위해서 A : 1, E : 2, I : 3, O : 4, U : 5 로 인덱스를 설정해주고, 0번은 Empty로 설정했다.
즉, A의경우 10000을, AAAE의 경우 11120을 의미하게 된다.
이렇게 치환을 하면 bfs를 통해 10000, 11000 등의 시퀀스를 구한 뒤 오름차순으로 sort만 해주면 된다.
이 때, 11011 등의 시퀀스는 등장하면 안되므로 10000, 11000 등 처럼 0이 항상 연속적으로 끝에 등장하는지 체크해줘야 한다.
코드는 아래와 같다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int result[5];
vector<string> global_result;
void bfs(int n, int depth)
{
if(depth == 5) {
if(result[depth - 1] == 0)
return;
string str = "";
for(int i=depth - 1;i >= 0;i--)
str.push_back(result[i] + '0');
bool is_fine = true;
for(int i = 1; i<str.size(); i++) {
if(str[i] != '0')
continue;
bool all_zero = true;
for(int j = i + 1; j<str.size(); j++) {
if(str[j] != '0') {
all_zero = false;
break;
}
}
if(!all_zero) {
is_fine = false;
break;
}
}
if(is_fine)
global_result.push_back(str);
return;
}
for(int i=0;i<n;i++) {
result[depth] = i;
bfs(n, depth + 1);
}
}
int solution(string word) {
int answer = 0;
vector<int> result;
string word_to_idx = "";
bfs(6, 0);
for(int i=0;i<word.size();i++) {
if(word[i] == 'A')
word_to_idx.push_back('1');
else if(word[i] == 'E')
word_to_idx.push_back('2');
else if(word[i] == 'I')
word_to_idx.push_back('3');
else if(word[i] == 'O')
word_to_idx.push_back('4');
else if(word[i] == 'U')
word_to_idx.push_back('5');
}
while(1) {
if(word_to_idx.size() == 5)
break;
word_to_idx.push_back('0');
}
sort(global_result.begin(), global_result.end());
for(int i=0;i<global_result.size();i++) {
if(global_result[i].compare(word_to_idx) == 0) {
answer = i + 1;
break;
}
}
return answer;
}
풀고 다른 사람의 코드를 봤는데, O(문자열 길이)의 Constant 문제였다;
위 코드도 따지고보면 Constant이긴한데, 모든 문자열의 경우를 다 구하는 Constant라 상수 차이가 엄청 많이 난다.
문자열의 규칙을 잘 보면
A
AA
AAA
AAAA
AAAAA로 증가한다.
이 때 각 자리마다 A로 시작하는 문자열의 갯수를 구할 수 있는데,
5번째 자리가 A로 시작하는 문자열 :
AAAAA (1개)
4번째 자리가 A로 시작하는 문자열 :
AAAA (1개)
AAAAA, AAAAE, AAAAI, AAAAO, AAAAU (5개)
3번째 자리가 A로 시작하는 문자열 :
AAA (1개)
AAAA, ... AAAAU (6개)
AAAE, ... AAAEU (6개)
AAAI, ... AAAIU (6개)
AAAU, ... AAAOU (6개)
AAAU, ... AAAUU (6개)
2번째 자리가 A로 시작하는 문자열 :
AA (1개)
AAA ...
31 * 5 + 1 = 156개
1번째 자리가 A로 시작하는 문자열 :
A (1개)
AA ...
156 * 5 + 1 = 781개
따라서 주어진 문자열을 0부터 n까지 탐색하면서 각 문자의 Index와 각 문자가 AEIOU 상에서 사전상 문자인지 이용하면 된다.
(사전상 A는 0번, E는 1번 ... U는 4번)
-
"I" 의 경우
I는 AEIOU 상에서 2번째에 위치한다.
그렇다면 이 보다 앞선 문자열은 A로 시작하는 781개의 문자열, E로 시작하는 781개의 문자열이 있다.
따라서 1562개가 앞에 있는 것을 알 수 있다. -
"EIO"의 경우
첫 번째, E의 경우 AEIOU 상에서 1번째에 위치한다. A로 시작하는 781개의 문자열이 앞에 존재한다.
두 번째, I의 경우 AEIOU 상에서 2번째에 위치하고, A, E로 시작하는 156개의 문자열이 그 앞에 있다.
세 번재, O의 경우 AEIOU 상에서 4번째에 위치하고, A, E, I로 시작하는 31개의 문자열이 그 앞에 있다.
따라서 781x1 + 1 + 156x2 + 1 + 31x3 + 1 = 1189이 된다.
각 단계에서 1을 더해주는 이유는 공백을 체크하기 위함이다.
위 문장을 예시로 설명하면, AAAE가 AAA보다 뒤에 있는 문자열이다.
이는 E를 기준으로 E를 포함하는 것보다 그 위치를 공백으로 두는 것이 더 앞선 문자열이라는 것인데,
주어진 문자열의 각 자리마다 공백은 1번씩 포함될 수 있기 때문에 각 자리마다 1씩 더해줘야 한다.
781x1 + 156x2 + 31x3 + (문자열의 길이 == 3) 으로 계산해도 된다.
#include <string>
int solution(string word) {
int answer = 0;
string base = "AEIOU";
int num[5] = { 781, 156, 31, 6, 1 };
for(int i=0;i<word.size();i++) {
int idx = base.find(word[i]);
answer += idx * num[i];
}
return answer + word.size();
}당연히 결과는 위의 코드에 비해서 훨씬 빠르다.
