スキルツリー

コード#コード#

[私の答え]

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

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    string str;
    for(int i=0;i<skill_trees.size();i++)
    {
        vector<int> v;
        str = skill_trees[i];
        int flag=0;
        /* 해당 스킬트리에서 각 스킬들의 인덱스를 벡터에 삽입 */
        for(int j=0;j<skill.length();j++)
        {
            int index = str.find(skill[j]);
            v.push_back(index);
        }
        for(int k=0;k<v.size();k++)
        {
            for(int z=k+1;z<v.size();z++)
            {
                /* 앞 스킬 인덱스가 뒤 스킬 인덱스보다 크면 스킬트리에 어긋남; */
                if(v[z] != -1 && v[k] > v[z]) {
                    flag=1;
                    break;
                }
                /* 앞 스킬을 안찍었는데 뒤에 스킬이 찍혀있는건 말이 안됨; */
                if(v[k] == -1 && v[z] != -1) {
                    flag=1;
                    break;
                }
            }
            if(flag == 1) break;
        }
        if(flag == 0) answer++;
    }
    return answer;
}

解答法
1)与えられたスキルツリー(BSCDA)において、そのスキル(CBD)のインデックスをベクトルに保存する
2)ベクトルに格納されているインデックスが条件を満たす場合、count!

[別のコード]

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

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    string str;
    for(int i=0;i<skill_trees.size();i++)
    {
        vector<char> v;
        int flag=0;
        /* 해당 스킬트리에서 각 스킬의 문자를 벡터에 삽입 */
        for(int j=0;j<skill_trees[i].size();j++)
        {
            char st = skill_trees[i][j];
            for(int k=0;k<skill.length();k++)
            {
                char s = skill[k];
                if(st == s) v.push_back(st);
            }
        }
        /* skill의 인덱스와 비교해서 skill_trees에 존재하는 순서가
        skill순서와 일치하지 않으면 스킬트리에 어긋나는 것 
        (CB 처럼 D가 없는 경우도 있기에 v.size()를 해야함)*/
        for(int k=0;k<v.size();k++)
        {
            if(v[k] != skill[k]) {
                flag=1;
                break;
            }
        }
        if(flag == 0) answer++;
    }
    return answer;
}

1)スキルツリーで我々が望むスキルと比較し,発見時にベクトルに順番に挿入する.
2)ベクトルに存在する文字がskillの順序と同じである場合、count!