코딩테스트 : 스킬트리

해당 문제는 정해진 스킬 순서가 있고 해당 순서를 지킨 스킬 트리의 개수를 구하는 문제이다.

스킬에 저장된 원소들은 스킬 트리에서 순서대로 존재해야한다.

해결 방법

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    //스킬 트리 문자열을 한개 씩 읽어온다.
    for(string str : skill_trees)
    {
		    //가능한 스킬 트리인지 확인하는 변수
        bool can = true;
        //이후 배워야하는 스킬의 번호
        int i = 0;
        //읽어온 스킬 트리 문자열에서 문자들을 한개 씩 읽어온다.
        for(char ch : str)
        {
		        //읽은 문자가 선행 스킬 트리에 있으면 몇번째 인지 저장
            int it = skill.find(ch);
            //만약 스킬 트리에 있다면
            if(it != string::npos)
            {
		            //읽은 문자와 선행 스킬의 배워야하는 번호가 일치하면
                if(i == it)
                {
		                //배워야하는 스킬 번호를 다음 번호로 변경
                    i++;
                }
                //스킬 번호가 일치하지 않으면 - 순서를 다르게 스킬을 배웠으면
                else
                {
		                //불가능한 스킬 트리로 판별
                    can = false;
                    //불가능하니 더 이상 해당 문자열은 확인 필요 없음
                    break;
                }
            }
        }
        //가능한 스킬 트리 였다면
        if(can)
		        //answer을 증가
            answer++;
    }
    return answer;
}

찍은 스킬 트리에서 선행 스킬이 있다면 해당 스킬이 순서대로 찍혔는지 확인하는 방법으로 구현하였다.