[Algorithm] 스킬트리

문제설명

스킬트리는 정해진 순서의 알파벳으로 이루어진 문자열 skill과 임의의 알파벳 문자열로 이루어진 배열 skill_trees가 주어질 때 skill_trees의 각 요소에서 skill의 알파벳이 포함된 경우 주어진 순서가 맞는 경우의 수를 합산하여 반환하는 문제이다.

문제해결

skill_trees 배열에 맞는 true 배열을 생성한 후 skill_trees의 각 요소를 순회하며 요소의 알파벳이 skill에 포함되있고 skill의 주어진 순서와 일치하면 탐색할 skill의 인덱스를 증가시키는 방식으로 true인 요소를 찾아나간다. 조건에 해당하지 않는다면 true로 초기화된 skill_trees 요소의 인덱스를 false로 재할당한다.

function solution(skill, skill_trees) {
    let able = new Array(skill_trees.length).fill(true);
    skill_trees.forEach((skill_tree,skill_treeIdx) => {
        let skillIdx = 0;
        for (let i = 0; i < skill_tree.length; i++) {
            const current = skill_tree[i];
            if (skill.includes(current)) {
                if (skill[skillIdx] === current) skillIdx++;
                else {
                    able[skill_treeIdx] = false;
                    break;
                }
            }
        }
    })
    return able.filter(e => e).length;
}