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

출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

 

 

먼저, 생각해야 할 부분

 

1. 이전 것이 무조건 전에 포함되어야한다.

 

단순히 스킬 트리 상에 존재하는 것이 스킬 순서만 지키면 되는게 아니라

CBD에서 B가 포함될 경우 C도 존재하여야 한다.

 

 

---

 

풀이

 

def solution(skill, skill_trees):
    skill_set = set([char for char in skill])
    count = 0

    for tree in skill_trees:
        order = ''.join([char for char in tree if char in skill_set])
        
        if skill.startswith(order):
            count += 1
            
    return count

 

이전의 것을 포함해야 하기 때문에 스킬 트리에서 CBD라는 스킬 순서의 스킬만 뽑을 경우

C는 무조건 존재하거나 모든 스킬이 들어가있지 않아야한다.

즉, 뽑은 것이 CBD 문자열의 시작 부분에 들어가있다면 포함된 것이므로

order에서 skill에 있는 문자를 skill_tree로부터 뽑아서 문자열로 만들고

startswith 함수를 사용해 skill의 시작부분에 위치하는지 확인하였다.

 

---

시간 복잡도

-

 

알게 된 점

 

-

 

고찰

 

-

 

Github

프로그래머스 - 스킬 트리