문제:
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 ->라이트닝 볼트 -> 썬더 일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 ->힐링->라이트닝 볼트->썬더 와 같은 스킬트리는 가능하지만, 썬더->스파크 나 라이트닝 볼트 ->스파크 ->힐링 -> 썬더 와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
풀이 방법:
skill의 인덱스를 비교했을 때 뒤의 스킬이 선행스킬보다 앞서서 있다면 잘못된 스킬트리인것이다. skill에 있는 것들이 항상 스킬트리에 있다는 보장이 없으므로 없는 것을 찾았을 때 -1을 반환하는 find를 사용했다. 따라서 나올 수 있는 경우의 수는 총 5가지이다. 편의상 이전의 스킬을 1번 스킬 이후의 스킬을 2번이라 표현한다.
1. 1번스킬의 인덱스 < 2번스킬의 인덱스 일 때
1번스킬이 존재하지 않고 2번스킬이 존재하거나 아니면 정상적으로 이루어져 있을 경우가 존재한다.
전자의 경우에는 잘못된 경우이므로 False로 설정하고 후자는 정상적인 경우이므로 True로 유지한채 진행한다.
2. 1번스킬의 인덱스 ==2번스킬의 인덱스 일 때
이 경우는 둘 다 -1로 같은 것 뿐이다. 예시에서 C만 존재하고 B ,D가 존재 하지 않는다면 이 또한 True이므로 그대로 진행한다.
3. 1번 스킬의 인덱스 > 2번 스킬의 인덱스 일 때
1번스킬은 존재하지만 2번 스킬이 존재하지 않거나, 잘못 스킬트리가 구성되어 있을 경우이므로 전자는 True로 진행, 후자는 False로 설정후 종료시켰다.
이 과정이 모두 끝나고 난 뒤에도 True이면 정상적인 스킬트리이므로 answer 카운트를 증가시켰다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def solution(skill,skill_trees): answer_count=0 for i in skill_trees: correct=True for j in range(1,len(skill)): if i.find(skill[j-1])<i.find(skill[j]): if i.find(skill[j-1])==-1: correct=False break elif i.find(skill[j-1])==i.find(skill[j]): pass else: if i.find(skill[j])==-1: continue correct=False break if correct: answer_count+=1 return answer_count | cs |
