(프로그래머스 c++)스킬트리

스킬 트리 문제..

우선 for문으로 skill_trees 에 들어가 있는 스킬 수 만큼 반복하자.

그리고 스킬의 인덱스를 체크하는 index 변수와 순서대로 스킬을 찍을 수 있는지 알 수 있는 cnt 변수,

스킬의 순서를 체크하는 before 반복자를 선언한다.

 

while문을 돌면서 순서에 맞게 찍을 수 있는지 체크하도록 하자.

우선 종료 조건으로 index가 스킬의 사이즈와 같다면 break를 걸어 탈출하도록 하였다.

아니라면 반복자 itr을 선언하여 skill_trees[i]에서 skill[index]의 위치를 찾아낸다.

만약 순서가 제대로 맞지 않는다면 즉, before 반복자가 itr 반복자보다 크다면

cnt를 0으로 만들고 탈출하도록 하였다.

순서대로 찍었다면 before 반복자는 itr 반복자보다 무조건적으로 작게 되니 index와 cnt를 ++해주고,

before를 itr로 바꾸어 현재 위치로 설정을 해놓는다.

 

while문을 탈출하여 cnt가 0보다 큰지 확인하고, 크면 answer++을 해주면 문제는 끝..!

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    for(int i = 0; i < skill_trees.size(); i++)
    {
        int index = 0, cnt = 0;
        auto before = skill_trees[i].begin();
        
        while(1)
        {
            if(index == skill.size())
                break;
            
            auto itr = find(skill_trees[i].begin(), skill_trees[i].end(), skill[index]);
            
            if(before <= itr)
            {
                index++;
                cnt++;
                before = itr;
            }
            else
            {
                cnt = 0;
                break;
            }
        }
        if(cnt > 0)
            answer++;
        
    }
    return answer;
}