[Python/파이썬] 프로그래머스 Summer/Winter Coding(~2018) 스킬트리

프로그래머스

코드

from collections import deque
# skill : 선행 스킬 순서
# skill_trees : 유저들이 만든 스킬트리를 만든 배열
def solution(skill, skill_trees):   
    answer = 0
    for i in range(len(skill_trees)):
        skill_deq  = deque(list(skill))
        flag = True
        for s in skill_trees[i]:
            if not skill_deq:
                break
            if s == skill_deq[0]:
                skill_deq.popleft()
            else:
                if s in skill_deq:
                    flag = False
                    break
        if flag:
            answer += 1
    return answer

선행 스킬이 있는 스킬의 경우 순서대로 배워야만 한다. 

앞순서의 스킬들부터 뽑아주기 위해 선행스킬 순서가 담긴 배열 skill을 deque로 만들었다.

이제 스킬트리의 스킬을 하나씩 살펴보며 가능한 스킬트리인지 확인해본다.

1. 지금 나온 스킬이 skill_deq[0]과 일치한다면 skill_deq[0]을 pop해준다.
2. 일치하지 않는데 skill_deq에 있는 스킬이라면 이건 스킬트리 순서를 어긴 것이므로 flag를 False로 해주고 break한다.
3. 만약 deque로 만들어준 skill_deq이 비었다면 선행스킬 순서대로 다 배운 것이므로 이 스킬트리는 가능한 스킬트리이다. 따라서 더이상 탐색을 하지 않고 break해준다.

모두 살펴본 뒤 flag가 True라면 가능한 스킬트리이므로 answer += 1을 해준다.