코딩테스트 : 스킬트리 구현 자세히 파헤쳐보기 (Python3)

---

문제: 스킬트리

문제 설명:

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

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

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

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

제한 조건

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

 

def solution(skill, skill_trees):                           # 입력 : "CBD", ["BACDE", "CBADF", "AECB", "BDA"]
    numOfAvailableSkilltrees=0                              # 사용 가능한 스킬트리의 개수
    skill_level = 0                                         # 스킬트리 레벨 (레벨에 따라 배울 수 있는 스킬이 달라짐)
    for eachSkillTree in skill_trees:                       # 각 스킬트리 리스트에서 스킬트리(문자열) 호출
        for eachChar in eachSkillTree:                      # 스킬트리(문자열)에서 각 문자 호출
            if eachChar in skill:                           # 각 스킬(문자)이 필요로 하는 선행 스킬이 있는지 확인
                if skill_level == skill.index(eachChar):    # 스킬이 필요로 하는 선행스킬의 레벨에 도달했는지
                    skill_level += 1                        # 스킬 레벨 증가
                else:                                       # 스킬의 레벨이 충분치 않아 스킬을 배울 수 없음
                    break                                   
        else:                                               # break를 통해 for문을 빠져나오지 않은 경우 통과
            numOfAvailableSkilltrees += 1                   # 유효한 스킬트리 개수 증가
        skill_level = 0                                     # 각각의 스킬트리를 검토 후 스킬레벨 초기화
    return numOfAvailableSkilltrees

​

 

KEYPOINT

 

1. For else 문

For문에서 break문을 이용하여 루프를 빠져나오지 않았을때 else의 구문을 실행한다.

2. 리스트에서 list.index(x)

list라는 배열에서 x의 위치를 반환해준다. (x가 존재하지 않는다면 -1을 반환)

 

파리의 센느 강