[Programmers] 스킬트리

*스킬에 있는 문자의 순서를 인덱스화했다. 

indegree[26]은 스킬의 문자의 위치를 저장한다. 

스킬이 "CBD"라면 

0

2

1

3

0

0

0

0

0

0

이렇게 저장이 되어있다. 

 

*스킬트리에 있는 문자 중 스킬에 속한 문자들은 각 indegree[] 에 저장된 숫자로 치환한다. 

*숫자가 1씩만 증가하는 순서로 되어있어야 하기 때문에 idx 변수에 값을 저장해서 1씩 증가하는지 확인한다. 

 

 

#include <string> #include <vector> #include <iostream> #include <algorithm> #define INF 987654321 using namespace std; int indegree[26] = {0}; int solution(string skill, vector<string> tree) { int answer = 0; for (int i = 0; i < skill.size(); i++) { indegree[skill[i]-'A'] = i+1; } // for (int i = 0; i < 26; i++) cout << indegree[i] << '\n'; //1-> 2->3 이렇게 나와야 한다. for (int i = 0; i< tree.size(); i++) { int flag = true; string ns = ""; int idx = 0; for (int j = 0; j<tree[i].size(); j++) { if (!indegree[tree[i][j] - 'A'] ) continue; if (idx == indegree[tree[i][j] - 'A']-1 ) { idx = indegree[tree[i][j] - 'A']; } else { flag = false; break; } } if (flag) { answer++; } } return answer; }