[Programmers]#Level2_스킬 트리, find 알고리즘

 

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. find 알고리즘

[Basic C++] #43_STL 알고리즘, find, find_if

 

C++ 표준라이브러리에서 제공하는 find 알고리즘은 지정된 구간 내 특정 항목을 찾는 알고리즘입니다. find 알고리즘은 반복자를 매개로 컨테이너의 구간 내 인자로 주어진 특정 항목을 찾아서 해당 위치의 반복자를 반환합니다. 만약, 찾고자 하는 항목이 지정된 구간 내 존재하지 않을 경우, end 반복자를 반환합니다.

 

2. 선행 순서를 카운트하고, 현재 스킬이 선행 순서를 지키는지 확인!

1. 먼저, skill_trees를 순회합니다. 
2. 각 스킬 순서를 문자 단위로 순회하며, 각 문자가 스킬 트리에 존재하는지 확인합니다.
3. 만약, 특정 스킬이 스킬 트리에 존재하지 않다면, 다음 스킬로 넘어갑니다.
4. 만약, 특정 스킬이 스킬 트리에 존재한다면, 스킬 트리 선행 순서가 맞는지 확인합니다. 이때, 현재 스킬 선행 순서와 현재 스킬의 순서와 다를 경우, 해당 스킬 트리는 유효하지 않습니다. 반대로, 현재 스킬 선행 순서와 현재 스킬의 순서가 같을 경우, 스킬 선행 순서를 +1해 주고, 다음 스킬을 차례대로 순회합니다.
5. 위 과정을 반복하며, 유효한 스킬 순서를 카운트해줍니다.

 

---

 

#3. 코드

/*
    [문제] : 주어진 선행 스킬을 참고해 사용자들의 스킬 트리 가능성 여부 체크
    [설명]
            1. string을 순회하며, 각 char가 skill 목록의 올바른 순서에 위치하는지 find() 알고리즘 활용
*/

#include <string>
#include <vector>
using namespace std;


int solution(string skill, vector<string> skill_trees) {
    int answer = 0;

    for(const auto& skill_tree : skill_trees)
    {
        int presiquisite = 0;
        bool IsVaild = true;

        for(const auto& c : skill_tree)
        {
            auto it = skill.find(c);
            if(it == -1) continue;

            if(it == presiquisite)
            {
                presiquisite++;
            }
            else
            {
                IsVaild = false;
                break;
            }
        }
        if(IsVaild) answer++;
    }

    return answer;
}

 

---