Algorithm/C++ - 프로그래머스
프로그래머스 Level 2 - 스킬트리 C++
ㅇㅇ잉
2021. 3. 5. 18:17
설명은 주석에 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int solution(string skill, vector<string> skill_trees) {
int answer = skill_trees.size();
//알파벳 순서대로 넣을거다! index 1=A,2=B ~
int arr[27]={0,};
int cnt=1; //선행스킬 순서 체크
for(int i=0;i<skill.length();i++){
arr[skill[i]-65] = cnt++;
}
for(int i=0;i<skill_trees.size();i++){
string str = skill_trees[i];
int find=1; //현재 스킬 순서
for(int j=0;j<str.length();j++){
if(arr[str[j]-65]==0) continue; //skill과 상관 없으면 continue;
//현재 찾은 스킬 순서와 다르면 불가능한
if(arr[str[j]-65]>find){
answer--;
break;
}
//같으면 find++;
else if(arr[str[j]-65]==find){
find++;
}
}
}
return answer;
}
|
cs |
풀이를 가져오진 않았지만 풀고 다른 분들은 어떻게 풀었나 싶어서 봤는데,
1. skill_trees를 비교하여 skill에 없는건 무시하고, 있는건 vector에 넣는다.
2. vector에 들어간 순서와 skill에 들어간 순서가 다르면 불가능한, 같으면 가능한
이런식으로도 풀 수 있다.