[프로그래머스 Level 2] 스킬트리 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(skill, skill_trees) {
    const preSkills = [...skill].reduce((acc, v) => {
        acc[v] = true;
        return acc;
    }, {});
    
    return skill_trees.reduce((acc, tree) => {
        const order = [...skill].reverse();
        for (const skill of tree) {
            if (!preSkills[skill]) {
                continue;
            }
            if (order.pop() !== skill) {
                return acc;
            }
        }
        return acc + 1;
    }, 0);
}

먼저 스킬 순서에 존재하는 스킬들의 목록을 객체로 만들어 key로 존재 여부를 바로 알 수 있도록 한 preSkills를 만든다. 그 다음 skill_trees를 순회하면서 스킬 순서를 역순으로 만든 배열을 order에 저장하고, skill_trees에 있는 스킬 트리들을 한 글자씩 순회한다. 이 때 선행 스킬 순서에 존재하지 않는 스킬이면 무시하고(continue), 존재하는 스킬이나 순서가 맞지 않는다면 카운트하지 않는다. 스킬 트리의 모든 스킬들을 순회하였다면 올바른 스킬 트리이므로 카운트한다. 이렇게 카운트한 스킬 트리의 개수를 세서 반환하면 된다.

 

이 문제에서는 skill의 길이가 최대 26으로 주어지기 때문에 이렇게까지 할 필요가 없다.

성능을 고려하지 않은 더 간결한 풀이는 아래와 같다.

function solution(skill, skill_trees) {
    return skill_trees.reduce((acc, tree) => {
        const order = [...skill];
        for (const curSkill of tree) {
            if (skill.indexOf(curSkill) === -1) {
                continue;
            }
            if (order.shift() !== curSkill) {
                return acc;
            }
        }
        return acc + 1;
    }, 0);
}