[Programmers] 스킬트리 (Python)

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

 

 

스킬 트리에서 선행 스킬 조건을 제대로 만족한 스킬트리의 개수를 찾는 문제!

오랜만에 게임이 하고 싶어지는 문제였다ㅋㅋ

 

처음에는 선행 스킬 조건을 Parents 테이블로 찾아야 하나 했는데 생각해보니 단계 순서를 정확하게 따르지 않으면 무조건 틀리기 때문에 

그냥 순서를 지켰느냐만 확인하면 되는 문제였다.

 

<풀이>

1. 각 스킬 레벨 정리

주어진 선행 스킬 순서대로 딕셔너리 형태로 0, 1, 2, ... 순으로 레벨을 매겨주었다.

 

2. 각 스킬 트리하나씩 살펴보며 선행 스킬 지켰는가 확인

i) 만약 선행스킬이 없는 스킬이라면 순서가 상관없으니 확인할 필요가 없음

ii) 선행 스킬이 있다면(스킬 딕셔너리에 존재한다면) 내가 현재 배울 수 있는 스킬인지 확인

-> 이때 배울 수 있는 스킬인지는 현재의 스킬 레벨을 통해 확인해주었다!

 

def solution(skill, skill_trees):
    answer = 0
    
    # 각 스킬 레벨 정리
    skill_dict = dict()
    for idx, value in enumerate(skill) :
        skill_dict[value] = idx
    
    for skill_tree in skill_trees :
        skill_level = 0
        flag = True
        for sk in skill_tree : # 스킬 하나씩 살펴보기
            if sk in skill_dict.keys() : # 선행 스킬이 있는 스킬이면
                if skill_dict[sk] == skill_level : # 현재 내가 배울 수 있는 스킬이면
                    skill_level += 1
                else :
                    flag = False
                    break
        if flag :
            answer += 1
            
    return answer