스킬트리.md

스킬트리

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

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

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

🧐 아이디어

스킬은 순서대로 배워야 하는 조건이 있으므로, Queue를 사용해 skill_tree 의 각 스킬과 비교해 보자.

var 스킬큐 = [C,B,D]

// 스킬트리 = "BACDE"
for 스킬 in 스킬트리 {
    만약 스킬큐에 포함되지 않는 스킬이면 {
        건너뛴다
    }

    만약 스킬큐가 비었다면 {
        순서대로 스킬을 배웠으므로, 뒤의 스킬을 볼 필요없다. 반복문 종료
    }

    만약 스킬 != 큐.front {
        순서대로 스킬을 배우지 않았다.
        return false
        // B(현재스킬) != C(큐.front)
    }

    만약 스킬 == 큐.front {
        배울 스킬이 맞다!
        큐.dequeue
        다음 반복문을 계속 돈다
    }
}

💻 구현

func solution(_ skill:String, _ skill_trees:[String]) -> Int {

    var skillQueue = Queue<Character>()

    for c in skill {
        skillQueue.enqueue(c)
    }

    var count = 0
    for skill_s in skill_trees {
        var queue = skillQueue
        var isOk = true
        for c in skill_s {
            if !skill.contains(c) {
                continue
            }
            if queue.isEmpty() {
                break
            }
            if c != queue.peek() {
                isOk = false
                break
            }
            // 배울 스킬이 스킬트리에 포함된다
            if c == queue.peek() {
                queue.dequeue()
                continue
            }
        }
        // 루프를 다 돌고나서, 스택이 비었다면 스킬트리 조건에 만족한 것
        if queue.isEmpty() || isOk {
            // 스킬트리를 모두 만족했음
            count += 1
            continue
        }
    }

    return count
}