프로그래머스 LV2 스킬트리

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

프로그래머스

 

문제

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

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

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

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

 

 

정답

 

//일단 1차 전직 스킬이 잇어야 한다

function solution(skill, skill_trees) {
    let answer = 0
    skill_trees.forEach((skill_tree,index)=>{
        let stack = []
        let canAnswer = true
        for (let i = 0; i < skill_tree.length; i++) {
            if (skill.indexOf(skill_tree[i]) >= 0) {
                let skillIndex = skill.indexOf(skill_tree[i])
                if (stack.length > 0 && stack[stack.length-1] + 1 === skillIndex ) {
                    stack.push(skillIndex)
                }
                else if (stack.length === 0 && skillIndex === 0) {
                    stack.push(skillIndex)
                }
                else {
                    canAnswer = false
                    break
                }
            }
        }
        if (canAnswer) answer++
    })
    return answer
}

해설 

1. skill을 순서대로 쌓아야하므로 이에 대한 분기 처리를 확실히 해야한다. 이 부분을 stack을 사용했다

만약 skill에 있는 문자이면

첫 번째 경우 stack의 제일 마지막 요소 즉 지금까지 쌓아온 skill의 최신 단계에 대한 그 다음 단계일때 stack에 추가한다

두 번째 경우 stack이 비어있고 지금 분기한 문자가 skill의 첫 번째 단계일 떄 stack에 추가한다

마지막 이 두 가지 경우가 아니면 잘못된 스킬트리이므로 답에 더하지 않게 boolean형을 통해 canAnswer = false를 넣어 추가되지 않게 한다