프로그래머스 - 모음사전 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

 

#include <string>
#include <map>
using namespace std;

int Cnt=1;
bool find=false;
void recur(string curs,string destWord)
{
    if(find)return;
    if(curs.length()==5)return;
    char ch[]={'A','E','I','O','U'};
    for(int i=0;i<5;i++)
    {
        if(curs+ch[i]==destWord)
        {
            find=true;return;
        }
        if(!find)
            Cnt++;
        recur(curs+ch[i],destWord);
    }
}

int solution(string word) {
    int answer = 0;
  
    recur("",word);       
    
    return Cnt;
}

 

모음으로만 만들수있는 길이 최대 5인 단어가 사전순으로 사전에 기록되어있을 때,

word가 몇번째에 위치했는지를 알아내면된다. 

 

재귀함수를 통해서 구현했다. 

현재 몇번째인지를 Cnt로, 재귀가 될 때마다 각 자리의 단어를 더해서 넘겨준다. 

 

처음 시작하고 'A'가 word랑 맞나 비교하고 아니면 재귀를 통해 "A" 를 넘겨준다.

그러면 다음 재귀에서는 'A' 를 기준으로 모음을 뒤에 붙여서 다시 word랑 비교한다.

이런식으로 단어 길이가 5가 될때까지 반복하며 재귀함수가 호출 될 때마다 Cnt를 증가시키면 사전순으로 몇번째인지 구할 수 있다. 

 

이 방법은 시간복잡도가 최대 O(5^5) 까지 걸린다. 또한 단어의 길이가 길어질수록 기하급수적으로 늘어난다. 

chatgpt는 이문제를 수학적인 방법으로접근해서 O(1)의 시간 복잡도를내는 코드를작성했다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string word) {
    int answer = 0;
    
    vector<int> base={781, 156, 31, 6, 1};
    vector<char> letter={'A','E','I','O','U'};
    
    for(int i=0;i<word.size();i++)
    {
        int idx = find(letter.begin(),letter.end(),word[i])-letter.begin();
        answer+= base[i]*idx+1;
    }
        
    
    return answer;
}

base는 이런 방식이다. 

'A'가 맨앞인 단어의 총 수는 5^4 이다. 거기서 A를 빼면 5^4-1 = 781 이다. 

즉, 각 자리에서 단어가 바뀌려면 얼만큼씩 건너뛰어야하는지를 미리 계산한 것이다. 

 

word만큼 for문을 돌며 find함수로 letter에 몇번째 인덱스인지 파악하여 

얼만큼 건너뛰어야 하는지를 base[i]*idx 로 구한다. 이 때, 인덱스는 0부터 시작이기 때문에 + 1을 해준다.