[Algorithm] 스킬트리

[hwangJi-dev]

💬 문제

스킬트리

💬 Idea

<스택의 원리를 사용하자>

1. 선수강되어야하는 skill 문자열을 배열형태로 바꾸어 stack을 만들어준다.
   1. skill: [”C”, “B”, “D”]
2. 가장먼저 선수강되어야하는 skill을 pop하여 target에 저장한다.
   1. target: “C”
   2. skill: [”B”, “D”]
3. 이후 skill_trees에 있는 각 스킬들을 돌면서
   1. currentSkill ≠ targetSkill (현재 수강하고자하는 스킬이 선수강되어야할 스킬이 아닌 경우)
      1. s가 skill에 포함된다면
         1. 선수강을 건너띄고 수강하는 경우이므로 허용될 수 없는 스킬트리이다. 따라서 available 변수의 값을 false로 바꾼 뒤 break로 반복문을 탈출한다.
      2. s가 skill에 포함되지 않는다면
         1. 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있기 때문에 아무런 조치를 취하지 않는다.
   2. currentSkill == targetSkill (현재 수강하고자하는 스킬이 선수강되어야할 스킬과 같은 경우)
      1. 선수강 스킬 스택의 첫번째 원소를 꺼내어 다음 targetSkill로 배정해준다.
4. 위 3번 로직을 실행한 후 available 변수의 값이 true라면 가능한 스킬트리를 의미하는 것이므로 sum에 1을 더해준다.

💬 풀이

func solution(skill:String, skill_trees:[String]) -> Int {
    var sum = 0
    
    for tree in skill_trees {
        var preSkillset = Array(skill).map{ String($0) }
        var targetSkill = preSkillset.removeFirst()
        var available = true
        
        for currentSkill in tree {
            if preSkillset.contains(String(currentSkill)) {
                available = false
                break
            }
            
            if String(currentSkill) == targetSkill && preSkillset.count > 0 {
                targetSkill = preSkillset.removeFirst()
            }
        }
        
        sum += available ? 1 : 0
    }
    
    return sum
}