[Algorithm] [Python] Programmers - 스킬트리

스킬트리

---

INDEX

• 문제 설명
• 입출력 예
• 제출 코드
• 코드 설명

---

문제 설명

---

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

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

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

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

제한 조건

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

입출력 예

---

skill : "CBD"

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

return : 2

제출 코드

---

def solution(skill, skill_trees):
    answer = 0
    skill_tech = list(skill)

    while skill_trees:
        skill_tech_idx = [0 for _ in range(len(skill_tech))]
        user_tree = skill_trees.pop(0)
        cnt = 0
        for i in range(len(user_tree)):
            cnt += 1
            if user_tree[i] in skill_tech:
                idx = skill_tech.index(user_tree[i])
                if 0 in skill_tech_idx[:idx]:
                    break
                else:
                    skill_tech_idx[idx] = 1

            if cnt == len(user_tree):
                answer += 1

    return answer

코드 설명

---

문제는 간단하다.

전달받은 유저의 스킬트리가 정석 스킬트리를 따르고 있는지만 검증하면 된다.

따라서, 우선 이를 검증하기 위한 배열 skill_tech_idx 를 만든다.

이후 유저의 스킬트리 원소를 하나씩 가져와서 문자를 하나 하나 비교한다.
만일 현재 문자가 skill에 포함 된다면 해당 문자 인덱스값을 가져온 이후, skill_tech_idx 배열의 시작부터 해당 인덱스까지 0이 있는지 확인한다. -> 해당 부분이 정석 테크를 타고 있는지 확인하는 부분이다.

만일 0이 없다면 해당 인덱스 위치의 값을 1로 수정하여 스킬을 배웠다는 것을 표시한다.

이를 반복하여 사용자의 스킬트리가 정석 스킬트리를 따르고 있는지 검증한다.

다른 사람의 풀이

---

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

파이썬만이 제공하는 for~else 문을 활용한 풀이다.

for~else는 for문이 중간에 break등으로 끊기지 않고, 끝까지 수행되었을 때 else문이 실행된다.

for문 내에서 어떠한 값을 검증하는데에 유용하게 사용될 것 같다.