[Programmers]Python_스킬트리

문제

 

문제 설명

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

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

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

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

 

제한사항

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

 

코드

from collections import deque
def solution(skill, skill_trees):
    answer = 0

    for tree in skill_trees:
        skill_list = deque(skill) #스킬순서

        for cur_skill in tree: #현재 스킬트리
            #순서가 있는 스킬이고 선행스킬을 아직 배우지 않은 거라면 break
            if cur_skill in skill and cur_skill != skill_list.popleft():
                break
        #for 반복문이 끝까지 진행됬다면 사용가능한 스킬트리이므로 answer += 1
        else:
            answer += 1

    return answer

 

진행 과정

 

예제 #1

skill = "CBD"

skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]

 

처음엔 skill의 index를 따로 저장해서 순서를 비교하는 방식으로 진행하다가 그럴 필요가 없어서 바로 수정하였다.

 

우선 skill_list 안에 없는 skill은 무시하면 됩니다. 그리고 skill_list 안에 있는 skill만 신경쓰면 된다.

 

현재 tree의 skill을 확인하다가 해당 skill이 skill_list 안에 있다면 무조건 첫 번째 skill이어야 합니다. 첫 번째 skill은 선행스킬도 필요없으니...

 

두 번째 skill부터는 선행 스킬이 있어야지 배울 수 있어서 확인을 해야되겠다고 생각할 수 있지만 그냥 두 번째로 배울 수 있는 skill인지 아닌지만 확인하면 된다.

 

이 과정은 deque의 popleft()를 사용하여 skill을 확인할 때마다 순서대로 배우는 건지 아닌지 check한다.

 

그리고 위에서 작성한 코드를 보듯이 for ~else를 사용하여 for 반복문이 모두 진행되면 해당 스킬트리는 사용가능하는 것을 의미한다. 사용 불가하다면 중간에 있는 if문에서 break가 걸려서 else문까지 가지못한다.

 

코드 진행은 다음과 같다

 

1) tree = "BACDE"
2) skill_list = deque(['C', 'B', 'D'])
3) cur_skill, skill_list.popleft() = B, C #순서가 안맞으므로 break

4) tree = "CBADF"
5) skill_list = deque(['C', 'B', 'D'])
6) cur_skill, skill_list.popleft() = C, C
7) cur_skill, skill_list.popleft() = B, B
8) cur_skill, skill_list.popleft() = D, D

9) tree = "AECB"
10) skill_list = deque(['C', 'B', 'D'])
11) cur_skill, skill_list.popleft() = C, C
12) cur_skill, skill_list.popleft() = B, B

13) tree = "BDA"
14) skill_list = deque(['C', 'B', 'D'])
15) cur_skill, skill_list.popleft() = B, C #순서가 안맞으므로 break