[프로그래머스 lv2] 스킬 트리 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

문자열 s가 스킬 순서를 만족하는지 확인하는 과정은 다음과 같다.

1) 문자열 s를 순회하면서 각 문자가 주어진 skill 에 포함되어있는지 확인한다.

2) skill에 포함되어있다면, 스킬 중 몇번째 순서인지 인덱스를 확인하여 기록해놓는다.

3) 문자열을 모두 순회하고 기록된 인덱스를 보았을 때, 기록된 인덱스는 0부터 시작하고 1씩 증가하는 오름차순 배열이어야 한다. 해당 조건을 만족한다면 스킬 순서를 지키는 문자열로, 만족하지 않는다면 스킬 순서를 지키지 않은 문자열로 판단한다.

 

skill_trees로 주어진 문자열 중에서 스킬 순서를 지키는 문자열의 개수를 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

bool check(string s, string skill) {
    
    vector<int> v;
    
    for (auto x : s) {
        int i = skill.find(x);
        if (i == string::npos) continue;
        v.push_back(i);
    }
    
    for (int i=0; i<v.size(); i++) {
        if (v[i] != i) return false;
    }
    return true;
}

int solution(string skill, vector<string> skill_trees) {
    
    int cnt = 0;
    for (auto s : skill_trees) {
        if (check(s, skill)) cnt++;
    }
    return cnt;
}