프로그래머스/윈터코팅2018/스킬트리

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

알고리즘 연습 - 스킬트리 | 프로그래머스

드디어 프로그래머스 코딩테스트에 나왔던 기출문제를 건드리고 있다.

이 문제는 각 skill_trees 원소의 string을 차례로 탐색하면서 핵심 skill에 해당하는 char가 있으면 이를 차례대로 queue에 집어 넣었다가,

queue에서 다시 한개씩 꺼내서 q의 사이즈만큼 순회하면서 핵심 스킬의 앞부분과 하나씩 비교하는 방식으로 가능한 스킬트리인지를 확인하였다.

아직, 그래프의 위상정렬은 익숙하지 않기 때문에 queue의 특성을 이용하여 풀어보고자 하였는데, 간신히 통과하였다 .. (공부가 많이 필요하다 아직)

[구현 코드]

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

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    string tmp;
    queue<char> q;
    for(int i = 0; i < skill_trees.size(); i++){
        for(int j = 0; j < skill_trees[i].size(); j++){
            for(int k = 0; k < skill.length(); k++){
                if(skill[k] == skill_trees[i][j]){
                    q.push(skill[k]);
                }
            }
        }
        if(q.empty()) answer++;
        //각 skill_tree의 원소별로 체크
        int m = 0;
        int size = q.size();
        int cnt = 0;
        while(!q.empty()){
            char now = q.front();
            q.pop();
            if(skill[m] == now){
                cnt++;
            }
            if(cnt == size){
                answer ++;
                break;
            }
            m++;
        }
    }
    return answer;
}