programmers - 스킬트리 with JS

Problem

출저: 프로그래머스

Solve

일단 특정 스킬이 스킬트리에 들어있는지 확인하기 위한 용도로 skillTree map(or dictionary)를 만든다

const getSkillMapFrom = skill => {
  const skillMap = {};
  skill.split("").forEach(el => {
    skillMap[el] = true;
  });
  return skillMap;
};

하나의 스킬트리가 가능한지 확인하는 함수를 만든다. 이때 skill 을 Que 자료구조에 넣어서 하나씩 뽑으면 순서가 보장되는지 확인이 가능하다. 스킬트리와 관련이 없는 경우를 제외하면 Q에서 뽑아낸 값과 현재 스킬값이 일치해야 한다. 그렇지 않으면 유효한 스킬트리가 아니다.

const isPossibleSkillTree = (skillTree, skillMap, skillQue) => {
  return skillTree.every((skill, i, arr) => {
    const isUnrelatedSkill = !skillMap[skill];
    if (isUnrelatedSkill) return true;
    if (skillQue[0] === skill) {
      skillQue.shift();
      return true;
    }
    return false;
  });
};

위 함수를 조합하여 solution 함수를 만든다.

function solution(skill, skillTrees) {
  const skillMap = getSkillMapFrom(skill);
  const skillQue = [...skill];
  const answer = skillTrees.filter(skillTree => {
    return isPossibleSkillTree([...skillTree], skillMap, [...skillQue]);
  }).length;
  return answer;
}