[Python] 스킬트리 - Summer/Winter Coding(~2018)

<문제 링크>

 

programmers.co.kr/learn/courses/30/lessons/49993

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

 

---

<풀이>

 

선행 스킬이 필요한 스킬을 배우기 위해서는 전 단계 스킬을 미리 배워야한다.

그렇기 때문에 skill_success에 배울 수 있는 모든 스킬트리를 담는다.

ex) skill_success = [ "", "C", "CB", "CBD" ]

여기서 중요한 건 ""(빈 공간)이 있어야 하는 이유다.

유저가 만든 스킬트리가 선행 스킬이 필요 없는 스킬들로 구성된 스킬트리라면 ?

==> 선행 스킬 조건에 맞지 않아도 되기 때문에 ""으로 조건 확인을 하면 된다.

위에서 배울 수 있는 스킬트리를 확인하는 조건들을 정리했다.

다음 과정들은 비교만 해주면 되기 때문에 비교적 쉽다.

이제 유저가 만든 스킬트리에서 선행 스킬에 속한 스킬(C or B or D)들을 추출해낸 후에

in 연산자를 통해 skill_success에 속했는지, 안 했는지를 판별하면 된다.

 

---

<코드>

skill: 선행 스킬 순서

skill_trees: 유저들이 만든 스킬트리를 담은 배열

skill_success: 선행 스킬 조건에 맞아 배울 수 있는 스킬트리

skill_role: 커스텀 스킬트리에서 skill에 속한 스킬을 담는 변수

---

def solution(skill, skill_trees):
    answer = 0 # 정답
    skill_success = [""]
    
    for i in range(len(skill)): # 선행 스킬 조건에 맞아 배울 수 있는 스킬트리
        skill_success.append(skill[0:i+1])
    
    for i in skill_trees:
        skill_role = "" # 규칙에 맞는 스킬트리인지 판단하는 변수
        
        for j in i:
            if j in skill: # j가 선행 스킬 순서에 포함될 경우
                skill_role += j
            
        if skill_role in skill_success: # 조건에 맞으면
            answer += 1
    
    return answer