스킬트리 (lv2)

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

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

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

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

제한조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 "CBD"로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

---

 처음에 문제를 제대로 읽지도 않고 skill 이 skill_tree안에 무조건 포함되어 있어야 한다고 생각하여 LCS로 접근했다. 스킬트리와 스킬의 LCS를 구한 뒤 그 길이가 스킬의 길이와 같을때마다 answer값을 1씩 더해주는 방법으로 접근했으나, 이내 틀렸다는 것을 알고 방향을 전환했다. 하지만 또 다시 문제를 잘못파악해서, 이번엔 스킬들의 순서만 맞으면 정답으로 처리한다고 생각해서 이진 탐색으로, 정확히는 lower bound 로 접근해서 원하는 스킬 순서가 나오는지만 확인했으나, 보기좋게 틀렸다. LCS와 lower bound 의 접근이 너무 익숙한 나머지 문제를 제멋대로 해석해서 쓸데없이 긴 시간을 낭비한 문제이다. 사실 문제에서 요구하고 있는 사항은 훨씬 간단한데, 무조건 스킬의 순서가 지켜져야 한다는 것이다. 예를 들면, 잘못 생각했을 때는 skill 이 "CBD"로 주어졌다고 했을 때 "B->D"로 나와도 정답이 된다고 생각했으나 사실 "C->D"와 같이 먼저나와야 하는 스킬이 선행되어야 하는 것이다. 따라서 본 문제에서의 올바른 접근은 스킬트리를 순회하며 주어진 순서에 맞게 나오는지만 확인하는 간단한 방법이라고 할 수 있다.

from collections import deque

def solution(skill, skill_trees):
    answer = 0
    skill_set = set(skill)
    for skill_tree in skill_trees:
        q = deque(skill)
        for c in skill_tree:
            if c in skill_set:
                if c == q[0]:
                    q.popleft()
                else:
                    break
        else:
            answer += 1
    return answer