프로그래머 스 모음 사전 - peulogeulaemeo seu mo-eum sajeon

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

-> 총 5개의 알파벳으로 길이가 1부터 5까지의 단어를 만듦

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

입출력 예wordresult

입출력 예 설명

입출력 예 #1

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2

"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3

"I"는 1563번째 단어입니다.

입출력 예 #4

"EIO"는 1189번째 단어입니다.

=> 여기 이해가 중요

가장 마지막(5번째) 알파벳은 A, E, I, O, U 를 각각 넣어서 바꿀 수 있음 

즉 마지막 단어를 바꾸려면 1번씩 바꾸면 됨

그렇다면 4번째 단어를 A, E, I, O, U 순으로 바꾸려면 A, E, I, O, U를한번 쭉 돌고 바꿀 수 있으니까 1 * 5(A, E, I, O, U이 5개니까) + 1 == 6 이 됨

==> 3번째 단어를 A, E, I, O, U 순으로 바꾸려면 4번째를 한번 쭉 돌고 바꿀 수 있으니까 6 * 5 + 1 == 31 이 됨

==> 2번째는 31 * 5 + 1 == 156

==> 1번째는 156 * 5 + 1 == 781

이를 토대로 각 자리에 어느 단어가 올 때 그 단어가 어디 순서에 있는지 표현이 가능함 배열로 한다 치면

{	  A    E     I	   O	 U
	{ 1,  782, 1563, 2344, 3125 }, // 1 번째 단어 -> 2번째에 넘기는 값 * 5 + 1 (781)
 	{ 1,  157,  313,  469,  625 }, // 2 번째 단어 -> 3번째에 넘기는 값 * 5 + 1 (156)
 	{ 1,   32,   63,   94,  125 }, // 2 번째 단어 -> 4번째에 넘기는 값 * 5 + 1 (31)
	{ 1,    7,   13,   19,   25 }, // 4 번째 단어 -> 5번째에 넘기는 값 * 5 + 1 (6)
 	{ 1,    2,    3,    4,    5 }  // 5 번째 단어 -> 1번씩 넘기면
} // 5씩 곱하는 이유는 단어를 5개 사용하니까

-> 이런 식으로 각 단어가 몇 번째에 오냐에 따라 필요한 값을 구할 수 있음

* A의 경우는 첫 단어이기 때문에 각 부분에 들어가면 당연히 1번만 넘어가면 되고* 근데 저걸 다 적어두거나 혹은 1, 6, 31, 156, 781을 미리 가지고 코드를 작성하면 너무 이 문제에만 적용이 가능하니까 상황에 맞게 1, 6, 31, 156, 781이 자동으로 들어오고 이 값들을 가지고 계산을 하게 하면 됨

프로그래머스 - 모음사전

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번)

1. "I" 의 경우
   I는 AEIOU 상에서 2번째에 위치한다.
   그렇다면 이 보다 앞선 문자열은 A로 시작하는 781개의 문자열, E로 시작하는 781개의 문자열이 있다.
   따라서 1562개가 앞에 있는 것을 알 수 있다.

2. "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();
}

당연히 결과는 위의 코드에 비해서 훨씬 빠르다.