[프로그래머스 고득점 kit] 모음사전 c++ (dfs, 사전순)

문제 링크

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

프로그래머스

 

문제 해설

dfs의 특성을 활용하여 사전순으로 완전 탐색을 진행할 수 있다. 따라서, 탐색 순서에 따라 진행하던 중, 찾고자하는 string이 나오면 해당 string의 순서를 리턴하면 된다.

 

 

dfs를 통한 사전순 완전탐색으로 순서 계산

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

string words="AEIOU";
string ans_str;
int num=-1;
int ans=0;
void dfs(string tmp){
    num++;
    if(tmp.compare(ans_str)==0){
        ans=num;
        return;
    }
    if(tmp.size()==5){
        return;
    }
    for(int i=0;i<5;i++){
        dfs(tmp+words[i]);
    }
}


int solution(string word) {
    int answer = 0;
    ans_str=word;
    dfs("");
    answer=ans;
    return answer;
}

 

 

+@ 위의 풀이도 시간초과가 생기지는 않지만, 아래와 같이 규칙성을 찾아서 푼다면 시간복잡도를 훨씬 감소시킬 수 있다.

#include <string>
#include <vector>
#include<iostream>
#include<map>
using namespace std;
map<char,int> parse;
int num[5]={781,156,31,6,1};



int solution(string word) {
    int answer = 0;
    vector<int> v;
    parse['A']=0;
    parse['E']=1;
    parse['I']=2;
    parse['O']=3;
    parse['U']=4;
    for(int i=0;i<word.size();i++){
        int tmp=parse[word[i]];
        answer+= (num[i]*tmp +1);
    }
    return answer;
}

//1562
//781  (문자)+ 5^4 (4자리) + 5^3 + 5^2+ 5^1  ( 1자리) =780+1( 해당 문자 1개만)
//
// A (1~ 780 )    E(781~ 1560)

//AAAAA
//A~~~

//E~~~~

//AEAEA

//A:0, E:1 , I: 2 , O:3, U:4

// 맨 뒤:() 1+1+1+1 +(1)  +1

// 2번쨰: 1+1+1+1+ (5)  +1 -> 4째자리에서 Ax 수-> 마지막자리 미정+ 마지막자리 없는 경우
//(AAAA)


// ( 5^4+5^3+5^2+5 (+1) ) *2 +1
// 

//1* 781 +1   + 2*156+1     +3*31 +1
// 781  312   93
//1093+93     

//781*1+1   + 156*2+1

// +1 +1 +1 +1