스킬트리
문제설명
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크->라이트닝볼트->썬더 일때, 썬더를 배우려면 먼저 라이트닝볼트를 배워야 하고, 라이트닝볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관 없이 배울 수 있습니다. 따라서 스파크->힐링->라이트닝볼트->썬더와 같은 스킬트리는 가능하지만, 썬더->스파크나 라이트닝볼트->스파크->힐링->썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return하는 solution 함수를 작성해주세요.
제한 조건
- 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 스킬 순서와 스킬트리는 문자열로 표기합니다.
- 예를 들어,
C->B->D라면 "CBD로 표기합니다.
- 예를 들어,
- 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
- skill_trees는 길이 1 이상 20 이하인 배열입니다.
- skill_trees의 원소는 스킬을 나타내는 문자열입니다.
- skill_trees의 원소는 길이가 2 이상 26이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.
입출력 예
skill = 'CBD'
skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]
return 2마지막 BDA같은 경우에도 B스킬은 C스킬이 선행되어야 하므로 불가능한 스킬트리이다
접근방법
음... Python for else문 찾아보다가 발견한 문제...
일단 먼저 드는 생각은 필요없는 스킬은 skill_trees에서 지워버리는것(?)이다.
예를 들어서
skill = "CBD"
skill_tree_1 = "AECB"
skill_tree_2 = "BDA"
skill_tree_3 = "DCKF"
일때
(선행스킬순서) C,B,D가 아닌 스킬은 스킬트리에서 지워버리고~
skill_tree_1 = "CB"
skill_tree_2 = "BD"
skill_tree_3 = "DC"
skill 변수에 할당된 "CBD"를 리스트 인덱스화 하면
0 = C
1 = B
2 = D
이다.
또한 스킬트리 변수에 할당된 스킬들도 리스트 인덱스화 하면?
skill_tree_1 : 0 = C, 1 = B
skill_tree_2 : 0 = B, 1 = D
skill_tree_3 : 0 = D, 1 = C
아 그냥 무조건 인덱스가 같아야되는구나?
아니 두 개의 리스트,
즉 선행스킬순서가 들어가있는 skill 리스트와
사용자의 스킬트리가 들어가있는 skill_tree_n 리스트가 같아야겠네?
만약 사용자의 스킬트리가 "CZZZZZZ"라면 "C"만 나오게하고...
이 길이만큼 skill 리스트를 잘라서 비교하면 되겠네
My Solution
def solution(skill, skill_trees):
answer = 0 # 가능한 스킬트리를 카운팅할 빈 변수
skill = list(skill) # 선행스킬순서 skill은 str?이므로 list화 해준다.
for skill_tree in skill_trees: # 사용자의 스킬트리를 하나씩 받기(for check)
skill_tree = list(skill_tree) # 사용자스킬트리 skill_tree를 list화 해준다.
tmp = [] # 잡스킬 지우고 난 후의 남은 스킬만 넣을 바구니
for s in skill_tree: # 사용자스킬트리 탐색
if s in skill:
tmp.append(s)
if tmp == skill[: len(tmp)]: # 잡스킬 지운 스킬트리 vs 선행스킬순서
answer += 1
return answersolution("CBD", ["C", "B", "BD", "CD", "ABCD", "ACBD", "CBD", "DC"])
3IDEA_1 : Intersection (교집합)
사용자의 스킬트리 : "AFBCDE"
선행스킬순서 : "CBD"
일때...
- 사용자의 스킬트리 순서를 훼손시키지 않고
- 선행스킬순서에 있는 스킬만 뽑아내고 싶음
- 즉... "ABCD" "BCD" not "CBD"
교집합 사용하면 되지않을까?
# Test 'Intersection'
skill = "CBD"
skill_trees = "AFBCDE"
print( set(skill) & set(skill_trees) )
>>> {'B', 'C', 'D'} # 오?
print( list( set(skill) & set(skill_trees) ) )
>>> ['C', 'B', 'D'] # 엥?
print( list( set(skill_trees) & set(skill) ))
>>> ['C', 'B', 'D'] # ㅠㅠIDEA_2 : pop?함수
