스킬트리
문제 설명
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
제한 조건
스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
스킬 순서와 스킬트리는 문자열로 표기합니다.
예를 들어, C → B → D 라면 CBD로 표기합니다
선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
skill_trees는 길이 1 이상 20 이하인 배열입니다.
skill_trees의 원소는 스킬을 나타내는 문자열입니다.
skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.
입출력 예
skill skill_trees return
"CBD" ["BACDE", "CBADF", "AECB", "BDA"] 2
입출력 예 설명
BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
CBADF: 가능한 스킬트리입니다.
AECB: 가능한 스킬트리입니다.
BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.
문제가 긴데
아무튼 내가 이해한 바 로는 주어진 skill과 skill_trees에서 skill_trees에서 skill과 겹치지 않는걸 제외했을때 , 그 다음 skill을 불필요한걸 제외시킨 skill_trees의 길이와 같게하여 두 개를 비교해서 같으면 되는것.
def solution(skill, skill_trees):
result = 0
skill = list(skill)
# tree = [] #이게 안에 for문 안에 있었어야 했다는걸 왜 인지못했을까.
for i in skill_trees:
tree = []
for j in list(i):
if j in skill:
tree.append(j)
print(skill, tree) # tree sorted(tree)
print(len(skill), len(tree))
print(len(skill[0:len(tree)]), len(tree))
# if (len(skill[0:len(tree)]) == len(tree)) and (skill[0] == tree[0]):
a = skill[0:len(tree)]
if a == tree:
print(a)
result += 1
tree = 0
return result
print(solution("CBD", ["BACED", "CBADF", "AECB", "BDA"]))
우선 처음에 tree를 for문안에 두지 않아서 코드 밑부분이 헛돌고 있었던걸 꽤 나중에 발견했고;;;
if (len(skill[0:len(tree)]) == len(tree)) and (skill[0] == tree[0]):이 부분도 생각해보니 시작의 기준이되는 skill의 첫글자와 tree의 첫글자만 비교할것이 아니라
그뒤도 같아야 하기때문에 그 아래의 코드로 수정했다.
정리하면 제출한 코드는 다음과 같다.
def solution(skill, skill_trees):
result = 0
skill = list(skill)
for i in skill_trees:
tree = []
for j in list(i):
if j in skill:
tree.append(j)
a = skill[0:len(tree)]
if a == tree:
print(a)
result += 1
tree = 0
return result
print(solution("CBD", ["BACED", "CBADF", "AECB", "BDA"]))다른 효율적인 코드가 상당히 많다.
하지만 그렇게 메모리를 많이 먹지 않아서 일단은 만족스럽지만 , 이곳엔 기재하지않지만 다른사람들의 코드를 통해서 더 효율적인 코드를 쓸수있도록 배워야겠다.
