스킬트리 (Python)

https://programmers.co.kr/learn/courses/30/lessons/49993

def solution(skill, skill_trees):
    answer = 0

    for skill_tree in skill_trees:
        buf = []
        for each_skill in skill_tree:
            if each_skill in skill:
                buf.append(each_skill)
        if buf == list(skill[:len(buf)]):
            answer += 1

    return answer

 

skill_trees에는 여러 스킬 트리들이 저장되어 있고, 이 각각의 스킬트리들이 skill의 순서대로 놓여있는지 판단해야 한다.

 

선후 관계의 순서가 지켜져야 하니까 처음에는 위상 정렬을 떠올렸다. 스킬트리는 실제로 위상 정렬의 대표적인 예시니까 말이다. 하지만 이 문제는 정렬의 문제가 아니라 제대로 정렬되어 있는지 판단하는 문제이므로 위상 정렬과는 달리 단순한 비교로 끝날 수 있다고 생각했다.

 

A와 B가 있을 때 B가 A 순서대로 놓여있는지 확인하기 위해서는 우선 B의 원소들이 A에 있는지를 확인해야 한다.

A에 존재하는 B의 원소들을 buf 라는 새로운 리스트에 추가한 뒤, 나중에 A와 buf를 비교해서 일치하면 True다.

단, buf ⊂ A 일 수 있으므로 A는 buf의 길이까지만 비교한다.