[Python] 스킬트리 - 프로그래머스 Lv2

"CBD"라는 스킬트리 skill이 주어진다. skill_trees의 스킬들은 skill 스킬트리의 순서를 무조건 따라야 하고, 선행 스킬을 무조건 진행해야 한다.

"CBADF"의 경우 중간 정해지지 않은 스킬이 들어가지만, CBD 순서대로 스킬을 완료했으므로 정답이다.

하지만 "BACDE"같은 경우에는 B가 C 스킬을 배우기도 전에 먼저 배우려고 해 정답이 아니다.

 

 

<알고리즘>

queue 자료구조를 활용해 스택을 구현할 것이다 (popleft 활용)

tree 스킬트리를 큐로 전환하고, 맨 앞인덱스가 skill에 포함되고 존재한다면 popleft로 삭제해준다.

하지만 skill에 포함되지 않는데 맨 앞 인덱스가 아니라면 선행스킬을 배우지 않고 먼저 나타난 것이기에 정답이 아니다.

이 때 위에서 설정한 is_tree를 False로 바꾸어주고,

그에 따라 answer 카운트업 여부를 결정해준다.

 

from collections import deque

def solution(skill, skill_trees):
    answer = 0

    for tree in skill_trees :
        is_tree = True
        q = deque(skill)
        for s in tree:
            if s not in q : continue
            if s == q[0] :
                q.popleft()

            else :
                is_tree = False

        if is_tree == True : answer += 1

    return answer
    
    
    
# ex ) solution("CBD", ["BACDE", "CBADF", "AECB", "BDA"])