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

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

프로그래머스

스킬트리 중에서 선행 스킬 순서에 포함된 스킬을 뽑았을때 
선행 스킬 순서  원소 i,j의 순서가 스킬트리의 원소 i,j의 순서와 같으면 된다.

선행스킬순서 : RSF이라면
스킬트리 중에서 F,R,S의 원소의 순서는 RSF순이어야 한다. 선행스킬순서에 포함되지 않은 스킬은 어디에 들어가도 상관없고 선행스킬순서에 포함된 모든 원소가 스킬트리에 포함될 필요는 없다.

풀이 
두가지 풀이로 풀어봤다.
-첫번째

1. abc 배열에 각 스킬이 선행 스킬 순서에 몇번째에 해당하는지 저장한다.
2. 스킬트리에 있는 스킬이 상관 없는 스킬이면 continue하고 
  상관있는 스킬이면 몇번째로 나왔는지 체크한다. 예제에 C의 순서가 1인데
  B가 스킬트리에 있는 스킬 중에서 제일 먼저 나올 경우 abc[skill_trees[i][j]-'A'는 2이고  index=1이기때문에
  가능한 스킬트리가 될 수 없다.

-두번째
첫번째와 비슷하지만 abc배열을 int 형이 아니라 bool 형으로 한다.
abc에는 선행스킬순서를 저장하지 않고 선행스킬에 해당하는 스킬인지만 저장한다.
위의 2번째 과정에서 선행스킬순서에 포함되는 스킬이라면 스킬트리에 있는 스킬과 같은 스킬인지 직접비교한다.
스킬트리에 있는 스킬이 다 선행스킬에 있는 것은 아니므로 선행스킬순서의 인덱스는 index ,스킬트리의 인덱스는 j로 한다.


주의

처음에 i+1이 아니라 i를 저장하였는데 그러면 첫번째 스킬에 0이 저장되어 선행트리스킬의 첫번째 스킬을 구분할 수 없게 된다.

 

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

using namespace std;

int abc[26];

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int size=skill.size();
    
    for(int i=0;i<size;i++){
        
        abc[skill[i]-'A']=i+1; //C: abc[2]=1 , B:abc[1]=2
        
        
    }
    int index=1;
    size=skill_trees.size();
    int cnt=0;
    for(int i=0;i<size;i++){
        index=1;
        for(int j=0;j<skill_trees[i].size();j++){
            if(!abc[skill_trees[i][j]-'A'])//0이면 순서와 상관 없는 스킬
                continue;
            else if(abc[skill_trees[i][j]-'A']==index){ //순서대로 나왔는지
                    index++;
                }
            else{
               cnt++;
               break;
            }
        }
         
    }
       
    
    answer=size-cnt;//안되는 개수 빼기
    return answer;
}

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

using namespace std;

//int abc[26];
bool abc[26];
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int size=skill.size();
    
    for(int i=0;i<size;i++){
        
        //abc[skill[i]-'A']=i+1; //C: abc[2]=1 , B:abc[1]=2
        abc[skill[i]-'A']=true; //C: abc[2]=1 , B:abc[1]=2
        
        
        
    }
    int index=0;
    size=skill_trees.size();
    int cnt=0;
    for(int i=0;i<size;i++){
        index=0;
        for(int j=0;j<skill_trees[i].size();j++){
            if(!abc[skill_trees[i][j]-'A'])//0이면 순서와 상관 없는 스킬
                continue;
            else if(skill[index]==skill_trees[i][j]){ //순서대로 나왔는지
                    index++;
                }
            else{
               cnt++;
               break;
            }
        }
         
    }
       
    
    answer=size-cnt;//안되는 개수 빼기
    return answer;
}