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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49993

프로그래머스

코드

from collections import deque
def solution(skill, skill_trees):
    cnt = 0
    for skill_tree in skill_trees:
        q = deque(skill)
        for i in skill_tree:
            if not q: #큐가 비었으면 스킬트리 O
                cnt += 1
                break
            if i == q[0]:
                q.popleft()
        else:
            for j in q:
                if j in skill_tree:
                    break
            else:
                cnt += 1
    return cnt

풀이

• skill_trees는 길이가 최대 20이므로, 완전 탐색으로 풀었다.
• 주의할 점은 큐가 비게되면 모든 스킬을 다 배운 것이기 때문에 스킬트리가 될 수 있지만, 큐가 남아도 스킬트리가 될 수있는 경우가 있다.
• 케이스 4의 AECB의 경우 CB를 배우고 D를 안배워도 CB는 순서대로 스킬을 배웠으니 스킬 트리가 될 수 있다.
• 그래서 skill_tree에 대한 for문을 다 돌고 else문에서 다시 큐의 모든 원소가 스킬트리에 있는지 없는지를 체크했다.