[c++][프로그래머스] 스킬트리

https://programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

스킬트리와 스킬 순서를 비교해서 순서대로 배운 경우에만 정답이 되는 문제입니다.

 

스킬트리 특성상 앞 스킬을 배우지 않으면 뒤 스킬을 배울 수 없으므로 스킬트리 앞 스킬부터 비교해서 있는 경우 index를 증가시켜가면서 비교합니다.

 

전부 비교한 후 스킬이 남아있지 않는다면 바로 정답을 증가시키고, 만약 스킬이 남아있다면 남아있는 스킬과 스킬트리를 비교해서 일치하는게 있는지 확인합니다. 이때, 일치하는 스킬이 있다면 순서가 뒤바뀐채로 찍혔으므로 올바르지 않는 스킬트리 이고, 일치하는게 없다면 그냥 스킬이 아직 덜 찍힌 것이므로 올바른 스킬트리가 됩니다.

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int count = skill.length();     // 스킬의 갯수
    
    for(int i = 0; i< skill_trees.size(); i++)
    {
        string str = skill_trees[i];        // 스킬트리 저장
        int len = str.length();
        int index = 0;                      // 길이와 인덱스
        
        for(int j=0; j< len; j++)
        {
            if(skill[index] == str[j])      // 스킬 앞에서부터 비교
            {
                index++;
                if(index == count)          // 순서대로 다 있는 경우
                    break;
            }
        }
        
        bool find = true;
        
        if(index == count)
            answer++;           // 다 순서대로 있다면
        else
        {
            for(int k=index; k<count; k++)
            {
                for(int m=0; m<len; m++)
                {
                    if(skill[k] == str[m])
                    {
                        find = false;
                        break;
                    }
                }           // 아닌경우 순서가 바뀐 경우가 있는지 체크
                
                if(find == false)
                    break;
            }
            
            if(find == true)
                answer++;
        }
    }
    
    return answer;
}