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

스킬트리

 

 

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

 

---

문제 설명

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

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

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

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

 

---

입출력 예

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

 

입출력 예 설명

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

---

풀이

 

def solution(skill, skill_trees):

    skill_dict = {}
    score_dict = {}
    trees_dict = {}
    answer = 0

    for l in range(len(skill)):
        skill_dict[l] = skill[l]

    for q in range(len(skill_trees)):
        score_dict[q] = 0
        trees_dict[q] = skill_trees[q]
        
    no = False

    for u_key, u_val in trees_dict.items():
        
        if no:
            no = False
            
        for s in u_val:
            if no: break
            
            for s_key, s_val in skill_dict.items():
                if no: break
                
                if s == s_val:
                    if score_dict[u_key] == s_key:
                        score_dict[u_key] += 1

                    else:
                        no = True
                        score_dict[u_key] = -1
                        
        if score_dict[u_key] != -1:
            answer += 1
    return answer