[Python] 스킬 트리

문제 설명

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

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

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

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

 

제한 조건

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

 

입출력 예

skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

 

• "BACDE": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• "CBADF": 가능한 스킬트리입니다.
• "AECB": 가능한 스킬트리입니다.
• "BDA": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

---

풀이

skill_trees에 있는 후보 중 몇 개가 가능한 스킬트리인지를 판별하는 문제라고 할 때,

후보의 알파벳이 skill에 있는 알파벳과 겹친다면 그 순서가 같아야 한다.

 

따라서 skill_idx가 후보의 알파벳이 skill의 알파벳과 겹치는 횟수로 선정하고

skill의 해당 index의 값이 후보의 알파벳 값과 같은 지를 판별한다. 

def solution(skill, skill_trees):
    '''
    skill: 선행 스킬 순서
    skill_trees: 유저가 만든 [유저가 스킬을 배울 순서]
    skill_trees에서 가능한 갯수 return
    '''
    cnt = 0
    for skills in skill_trees: #skills가 skill의 순서를 따르냐
    # 이전 요구 스킬을 모두 이전에 가지고 있어야 함
        flag = 1
        skill_idx = -1 # 실제 skill의 idx
        for s in skills:
            if s in skill:
                #print(s)
                skill_idx += 1
                if skill[skill_idx] != s:
                    flag = 0
        if flag == 1:
            cnt += 1
        print('\n')
        
    return

---

다른 풀이

 

1.

deque를 사용한다. 나의 풀이에서 index를 증가했다면 여기서는 값을 pop해준다.

from collections import deque

def solution(skill, skill_trees):
    answer = 0
    
    for skill_tree in skill_trees:
        queue = deque(skill)
        flag = 0
        
        for sk in skill_tree:
            if sk in skill:
                temp = queue.popleft()
                if sk != temp:
                    flag = 1
                    break
                    
        if flag == 0:
            answer += 1
            
    return answer

 

 

2.

startwith를 사용한다.

A.startwith(B)    => A가 B로 시작하는 지를 체크한다.

skill의 알파벳이 모두 후보에 등장할 필요는 없지만, skill의 i번째 값이 후보에서 등장했다면 skill의 i-1, i-2, ..., 0번째 값은 반드시 이미 후보에서 등장해야한다.

def solution(skill, skill_trees):
    answer = 0 

    for skill_tree in skill_trees:
        check = ""

        for i in skill_tree:
            if i in skill:
                check += i 
                
        if skill.startswith(check):
            answer += 1
    return answer

 

3. 

나의 풀이에서는 skill에 없는 알파벳도 순회해야해서 복잡했다.

처음부터 skill_trees의 후보에서 skill에 있는 알파벳만을 추출한다.

def solution(skill, skill_trees):
    skill_trees = ["".join((sk for sk in tree if sk in skill)) for tree in skill_trees]
    skill_trees = [
        all(((skill[index] == sk) for index, sk in enumerate(tree)))
        for tree in skill_trees
    ]
    return sum(skill_trees)

그리고 all을 사용하면 True면 1, False면 0이므로 sum을 해주면 True의 개수를 알 수 있다.