PR - 스킬트리

Goody·2021년 3월 22일
0

알고리즘

목록 보기
74/122

문제

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.


예시

skillskill_treesreturn
"CBD"["BACDE", "CBADF", "AECB", "BDA"]2

풀이

  1. skill_trees 배열을 돌면서, 원소들을 다시 하나의 배열 skillTree 로 취급한다.
  2. skillTree에는 skill과 상관 없는 스킬들이 섞여있으므로, filter 메서드로 걸러낸다.
  3. skill 배열을 돌면서 skillTree의 첫 번째 원소가 skill 배열의 i번째 원소와 일치하는지 검사하고, 일치하면 skillTree의 첫 번째 원소를 삭제한다.
  4. 3번 풀이로 인해 순서가 맞지 않는 스킬트리는 원소를 모두 없애지 못하고, 순서가 맞는 스킬트리만이 원소를 모두 없앨 수 있다.
  5. 따라서 skillTree의 길이가 0일 때, answer의 값을 1 늘린다.

코드

function solution(skill, skill_trees) {
    var answer = 0;
    let skillArray = [];
    let stack = [];
    let idx = 0;


    skill_trees.forEach((skillTree) => {
        skillArray = [...skill];
        let skillTreeArr = [...skillTree];

        skillTreeArr = skillTreeArr.filter((el) => {
            return skillArray.includes(el);
        });
       

        for(let i = 0; i < skillArray.length; i++) {
            if(skillArray[i] === skillTreeArr[0]) skillTreeArr.shift();
            else break;
        }

        if(skillTreeArr.length === 0) answer++;

    })


    return answer;
}
}

0개의 댓글