프로그래머스 - 스킬트리 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    for(auto& str : skill_trees)
    {
        vector<int> arr(26,0);
        for(int i=0;i<skill.length();i++)
            arr[skill[i]-65]=-1;

        int IdPointer=0;
        arr[skill[IdPointer]-65]=1;
        bool b=true;
        for(auto& c : str)
        {
            if(arr[c-65]==0||arr[c-65]==2)continue;
            else if(arr[c-65]==1)
            {
                arr[c-65]=2;
                IdPointer++;
                if(IdPointer<skill.length())
                    arr[skill[IdPointer]-65]=1;
            }
            else if(arr[c-65]==-1)
            {
                b=false;break;
            }
                
        }
        if(b)answer++;
    }
    
    return answer;
}

 

이 문제는 문자열을 보면서 해당스킬을 찍을 수 있는지 확인하는 것이다. 

선행 스킬이 있다면 그 스킬을 찍어야 다음스킬을 찍을 수 있는데 그것을 어떻게 확인할지가 문제였다. 

 

arr벡터를 만들어 각 스킬별로 상태를 표시하였다. 

-1 = 찍을 수 없는 스킬, 0 = 상관없는 스킬, 1 = 찍을 수 있는 스킬, 2 = 찍은 스킬

 

그리고 skill 문자열에서 현재 어느 스킬까지 찍었는지를 확인할 포인터로 IdPointer를 만들었다. 

 

skill[IdPointer]-65 가 0이라면 A를 뜻한다. 

arr[0] (=arr[A]) 가 만약 1이라면 찍을 수 있는 스킬이다. 

 

이런식으로 표시하여 skill_trees의 각 원소별로 체크한다. 

 

1. 상태를 초기화한다. 

2. 각 스킬별로 어떤상태인지 확인한다. 

 2-1. 0,2 면 패스 (선행이 없거나 이미 찍은스킬)

 2-2. 1이면 찍을 수 있는 스킬로 이 스킬을 찍으면 다음 스킬이 열린다. 따라서 idPointer를 1증가시킨다.

 2-3. 만약 -1 이라면 못찍는 스킬이므로 거기서 반복문을 종료한다. 

3. 만약 가능한 스킬트리면 answer를 1 증가시킨다. 

 

이런식으로 모든 원소를 순회한다.