[프로그래머스] 스킬트리 문제

Lv2문제입니다✍️

---

<문제 설명>

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

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

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

선행 스킬 순서 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 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

---

<내가 생각한 풀이>

입력이 문자열이기 때문에 list로 변환해주는 작업 먼저 진행,

전체 skill_trees의 개수를 count라는 값으로 선언

 

skill_trees안의 값을 한개씩 순회하며 skill의 값들이 각각 어디에 위치했는지 확인

skill값의 위치를 index라는 리스트에 담음

만약에 skill_tree의 값 안에 skill값이 존재하지 않을때는 skill_tree의 길이값을 넣어줌
(나올 수 있는 인덱스위치 보다 큰 값)

 

인덱스 값들이 순차적이지 않을 경우 불가능한 스킬트리 이므로 count -= 1해줌

최종적으로 count(가능한 개수)를 반환해주면 끝

def solution(skill, skill_trees):
    skill = list(skill)
    count = len(skill_trees)
    for tree in skill_trees:
        index=[]
        tree = list(tree)
        for skill_order in skill:
            if skill_order in tree:
                index.append(tree.index(skill_order))
            else:
                index.append(len(tree))
        if sorted(index)!=index:
            count-=1
    return count