스킬 트리

코드

[ 나의 풀이 ]

#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) 해당 skill_trees에서 우리가 원하는 skill들과 비교하며 발견 시 순서대로 벡터에 삽입
2) 벡터에 존재하는 문자들이 skill과 순서가 같으면 count!