프로그래머스 lv 2. 84512 모음사전 c++

 

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

#include <bits/stdc++.h>

using namespace std;

int cnt=-1;
int answer=0;
string target="";
string aeiou="AEIOU";

void dfs(string word){
    cnt++;
    if(word==target){
        answer=cnt;
        return;
    }
    if(word.length()>=5) return;
    for(int i=0; i<5; i++){
        dfs(word+aeiou[i]);
    }
}

int solution(string word){
    target=word;
    dfs("");
    
    return answer;
}

 

 

+++++++++++++++

#include <string>

using namespace std;

int solution(string word) {
    string v = string("AEIOU");
    int a = word.size();

    for(int i = 0, b = 1; i < word.size(); i++, b *= 5)
        a += v.rfind(word[i]) * 781 / b;

    return a;
}

 

다른 사람의 풀이를 보면 위와 같은형태의 781 이라는 상수를 사용하는 코드들을 볼 수 있는데, 이에 대한 이해가 잘 되지 않아서 781 이라는 상수는 어떤식으로 나온 수인가 궁금했는데, 이 수와 관련된 연산을 해서 사용하는형태의 코드를 작성하신 분이 올리신 블로그 게시글을 보고 이해가 가서 그 내용을 첨부해본다. 

  

https://ggjjdiary.tistory.com/68

[프로그래머스/C++] 모음사전

해당 작성자가 위와 같은 상수를 찾아내서 사용한 풀이도 같이 첨부해보자면, 

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(string word) {
    int answer = 0;
    map<char, int> alp;
    int next_word[5] = { 781, 156, 31, 6, 1 };
    
    alp.insert({'A', 0});
    alp.insert({'E', 1});
    alp.insert({'I', 2});
    alp.insert({'O', 3});
    alp.insert({'U', 4});
    
    int i = 0;
    for (const auto& w : word) {
        answer += 1 + alp[w] * next_word[i];
        i++;
    }
    
    return answer;
}
출처: https://ggjjdiary.tistory.com/68 [꼼지락 IT 공부방:티스토리]

이와 같은데, 해당 문제에서 주어진 문자들의 규칙상 위에 열거한 781, 156, 31, 6, 1 이라는 수들을 사용할 수 있게 되고, 

위에 언급한 다른 사람의 풀이에 등장하는 추천수 1등의 코드는 위와같은 수중에서 781을 이용해서 b로 나누면서 이용하는 형태다.