[프로그래머스] Lv.02 스킬트리 (JavaScript)

문제

프로그래머스

 

문제 설명

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

A스킬 -> B스킬 -> C스킬과 같은 순서로 되어 있다고 할 때 A스킬을 배우지 않고서는 B스킬을 배울 수 없고 B스킬을 배우지 않고서는 C스킬을 배울 수 없다는 것을 의미합니다. 하지만 A->B->C 스킬 트리가 있다고 했을 때 스킬 트리에 포함되지 않는 스킬들은 순서에 상관 없이 배울 수 있습니다. ex) A->D->B->C

선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매게변수로 주어질 때, 가능한 스킬트리 개수를 반환하면 되는 문제입니다.

 

※제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다. (A->B->C의 순서를 가진 스킬 트리의 경우 "ABC"형태가 됩니다.)
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복되지 않습니다.
• skill_trees는 길이가 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
• skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

풀이

문제에서 제시 된 바로는 스킬 트리에 포함되지 않은 스킬들의 순서는 신경쓰지 않는다고 되어 있습니다.

그렇기에 skill_trees의 각 요소를 순회하면서 skill_trees에 포함되어 있는 skill외의 다른 요소들을 제거해주고 possible이라는 임시 변수에 저장해주는 작업을 먼저 하였습니다.

그 다음으로 possilble의 요소가 skill값과 같은 순서로 되어 있는 지 확인하는 부분이 필요하였습니다.

possible의 경우 이미 skill에 존재하는 요소 만으로 filter된 배열이고, skill의 각 요소들이 possible에 순서 대로 저장 되어 있는지 확인해주는 작업만 해주면 되었기에 skill을 순서 대로 순회하면서 possible[0]과 일치하면 possible을 shift()해주었습니다.

그리고 skill_trees의 경우 skill의 모든 스킬을 배우는 것이 아니므로 불필요한 shift()를 발생할 수 있어, isPossible 변수를 선언하여 예외 처리를 해주었습니다.

아래는 풀이에 사용한 코드입니다.

function solution(skill, skill_trees) {
    var answer = 0;
    
    // skill_trees의 각 요소를 문자 단위로 구분해주는 작업
    skill_trees.map((skill_tree,idx) => {
        skill_trees[idx] = skill_tree.split("")
    })
    
    // skill의 각 요소를 문자 단위로 구분해주는 작업
    skill = skill.split('')
    
    // skill_trees의 각 요소를 순회
    skill_trees.map((skill_tree, idx) => {
    	// skill_tree에 있는 요소 중 skill의 요소를 제외한 나머지 요소를 삭제하는 작업
        const possible = skill_tree.filter((data)=> skill.includes(data))
        
        // 불필요한 shift() 방지
        let isPossible = true;
        // skill의 각 요소의 값을 순서 대로 possible[0]과 비교
        // 일치하면 shift해줍니다.
        skill.map((str) => {
            if(isPossible){
                possible[0] === str ? possible.shift() : isPossible = false
            }
        })
        
        // skill의 모든 요소가 shift되면 possible의 길이는 0이 되고,
        // 이는 스킬을 정상적으로 학습한 것이므로 answer의 값을 증가해줍니다.
        if(possible.length === 0) {
            answer++
        }
    })
    
    return answer;
}