[프로그래머스 Lv.2] 스킬트리 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49993

프로그래머스

풀이

스킬트리대로 스킬을 하나씩 배워나갈 때마다 해당 스킬이 선행 관계가 존재하는 스킬인 경우, 그 스킬이 순서에 맞게 배워졌는지 체크하고 만약 그렇지 않다면 이는 옳지 않은 스킬트리이므로 바로 배제하고, 스킬트리의 모든 스킬들을 모두 무사히 배웠다면 이는 올바른 스킬트리인 것이다. 즉, 스킬이 선행 관계가 존재하는 스킬인지 확인하는 로직과 순서에 맞게 배워졌는지 체크하는 로직을 코드로 구현하면 쉽게 풀 수 있는 문제이다.

 

먼저 스킬이 선행 관계가 존재하는 스킬인지는 skill 매개변수에 현재 스킬이 존재하는지 확인하면 되는 아주 간단한 로직이다. if in으로 확인할 수 있다.

다음으로 순서에 맞게 배워졌는지 체크하는 로직을 구현해야한다. 이는 선행 관계가 존재하는 스킬을 배운 순서대로 문자열에 담아두고, 이 문자열이 skill의 순서와 일치하는지, 즉 skill이 이 문자열로 시작하는지를 체크한다. 예를 들어, ACD 순서로 스킬을 배워야하고 현재 배운 스킬이 AD라면 ACD는 AD로 시작하지 않기 때문에 순서대로 스킬을 배우지 않았다는 것이고, 현재 배운 스킬이 AC라면 ACD는 AC로 시작하기 때문에 순서대로 스킬을 배워나가고 있다는 것이다.

 

위 방법들을 사용하여 풀이를 코드로 구현하면 아래와 같다.

def solution(skill, skill_trees):
    answer = len(skill_trees) # 모든 스킬트리가 가능하다고 가정
            
    for skill_tree in skill_trees: # 스킬트리 하나씩 순회하며
        cur_skills = ""
        for s in skill_tree: # 스킬트리의 스킬 하나씩 순회하면서
            if s in skill: # 선행 스킬을 체크해야하는 스킬이라면
                cur_skills += s # 현재 배운 스킬들에 추가
            
            if not skill.startswith(cur_skills): # 현재 배운 스킬들이 잘못된 스킬트리를 따라가고 있는 경우
                answer -= 1 # 정답에서 1을 빼고
                break # 해당 스킬트리는 배제
    
    return answer