[순서 확인 shift] 스킬트리

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

 

첫번째 방법 (성공)

필요한 스킬인지 빨리 탐색하려고 해쉬로 필요한 스킬을 정리 {skill이름: 번호}

각 트리마다 첫 스킬이 첫번째로 필요한 스킬이 아니면 다음 트리로 넘어간다

첫 스킬이 첫번째로 필요한 스킬이지만 다음 스킬이 순서가 틀려도 다음 트리로 넘어간다

여기서 순서가 맞는지 확인하는 법은 hash[전 스킬] +1 = hash[현 스킬] 이면 순서가 맞다.

이런식으로 전체트리를 순회한다.

function solution(skill, skill_trees) {
    var answer = 0;
    let queue = [];
    const obj = {};
    const firstSkill = skill[0];
    Array.from(skill).forEach((s, i) => obj[s] = i+1);
    
    // 트리
    for (const tree of skill_trees) {
        let isTree = true;
        // 트리 안의 스킬
        for (const s of tree) {
            if (!obj[s]) continue; // 스킬이외 문자는 스킵
            // 첫스킬
            if (!queue.length) {
                // 첫 스킬이 틀리면 다음 트리로
                if (s !== firstSkill) {
                    isTree = false;
                    queue = [];
                    break;
                }
                // 첫 스킬이 맞음 queue에 넣고 다음 스킬 검사
                queue.push(s);
            } else {
                const prev = queue[queue.length-1];
                // 미수행 선행스킬이 있을시
                if (obj[prev]+1 !== obj[s]) {
                    isTree = false;
                    queue = [];
                    break;
                }
                // 선행스킬을 수행했을때
                queue.push(s);
            }
            // 이미 스킬 다 했을때
            if (queue.length === skill.length) {
                break;
            }
        }
        // 스킬트리가 맞다
        if (isTree) {
            queue = [];
            answer++;
        }
    }
    return answer;
}

 

 

두번째 방법(성공)

첫번째 방법은 만약 스킬과 트리가 엄청 많다면 장점이 있지만

skill의 길이는 1 이상 26 이하 , skill_trees는 길이 1 이상 20 이하 여서 단순화 시켜서 정리했다

 

function solution(skill, skill_trees) {
    function check(tree) {
        const test = [...skill];
        for (const s of tree) {
            if (!skill.includes(s)) continue; // 스킬이외의 문자는 패스
            if (s === test.shift()) continue; // 스킬순서가 맞으면 패스
            return false; // 스킬순서가 맞지 않으면 false
        }
        return true;
    }
    return skill_trees.filter(check).length;
}