스킬트리

문제

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

 

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

 

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 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

 

테스트케이스

skill (string)	skill_trees(string [])	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2
"CBD"	["CAD"]	0
"CBD"	["AEF", "ZJW"]	2
"REA"	["REA", "POA"]	1
"CBDK"	["CB", "CXYB", "BD", "AECD", "ABC", "AEX", "CDB", "CBKD", "IJCB", "LMDK"]	4

---

풀이

1. Me

def solution(skill, skill_trees):
    answer = 0
    for i in skill_trees:  
        tmp = []
        for j in skill:
            tmp.append(i.find(j))  # 찾는 문자열이 없을 경우 -1 반환 
        
        num_cnt = tmp.count(-1)  
        # print(num_cnt, i, tmp)
        
        # [a,b,c,-1,-1] 과 같은 형태 (a < b < c) -> +1 
        # print(tmp[-num_cnt:] == [-1] * num_cnt) 
        if tmp[-num_cnt:] == [-1] * num_cnt:
            # print(tmp)
            if tmp[:-num_cnt] == sorted(tmp[:-num_cnt]):
                # print(tmp[:-num_cnt])
                answer += 1
        elif -1 not in tmp:
            if tmp == sorted(tmp):
                # print(tmp)
                answer += 1 
        # if tmp[-num_cnt:] == [-1] * num_cnt and 
        
        # 그외의 경우 -> continue 
    return answer

해당 문제를 풀기 위해 엄청나게 고민했다.. 단일 테스트케이스 통과는 되는데, 제출 후 채점하니 엄청나게 많이 틀려서 질문하기에 있는 테스트 케이스를 가져와 테스트케이스 실행을 통해 실험하며 작성한 코드 .. 

 

일단 스킬셋에 있는 스킬을 스킬트리에서 검색하고, 인덱스를 찾는다. (find 함수, 없을 경우 -1 반환) 스킬셋에 대해 인덱스를 가진 배열을 얻게 되었고, 이를 정렬하여 정렬한 경우 스킬 사용이 가능하다고 판단하였는데, 스킬셋에 스킬이 없는 경우는 -1을 반환하기 때문에 무작정 정렬해서 비교하면 틀린 답을 뱉어냈다.

 

* 주어진 스킬: "CBDK", 스킬트리: ["CB", "CXYB", "BD"]인 경우, tmp = [0, 1, -1, -1], [0, 3, -1, -1], [-1, 0, 1, -1]

 

고민에 고민을 한 결과, 스킬 발동이 가능한 스킬트리의 경우는 

1. 스킬트리가 주어진 스킬 + 기타 스킬로 구성된 경우 -> [a, b, c, ..., -1, -1], a < b < c 와 같은 형태일 경우 스킬이 발동된다. 스킬트리에 해당 스킬이 없을지라도 맨 마지막부터 순서대로 없는 경우라면 스킬 구현이 가능하다.

2. 스킬트리가 주어진 스킬로만 구성된 경우로, tmp에 -1이 없는 경우 -> [a, b, c], a < b < c와 같은 형태일 경우 스킬이 발동됨 

 

위 코드를 다시 정리하면 아래와 같다.

def solution(skill, skill_trees):
    answer = 0
    for i in skill_trees:  
        tmp = []
        for j in skill:
            tmp.append(i.find(j))  # 찾는 문자열이 없을 경우 -1 반환 
        num_cnt = tmp.count(-1)  
        if tmp[-num_cnt:] == [-1] * num_cnt:   # [a,b..d,-1,-1] 형태인 경우 
            if tmp[:-num_cnt] == sorted(tmp[:-num_cnt]):  # [a ~ d]가 정렬되어 있으면  
                answer += 1
        elif -1 not in tmp:   # 찾는 문자열이 모두 있고 
            if tmp == sorted(tmp):   # 순서대로 되어 있으면 
                answer += 1 
    return answer

 

2. Others

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)
        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1
    return answer

for ~ else 구문이 있다는 걸 위 코드를 통해 처음 알았다. skill_trees를 탐색하며, 각각의 스킬트리의 스킬이 스킬목록에 들어있고, 들어있는 스킬이 스킬 목록의 맨 앞 스킬과 다른 경우는 break한다.. answer이 1씩 증가하는 경우는 스킬트리의 스킬이 스킬 목록에 없거나, 들어있는 스킬이 스킬 목록의 맨 앞 스킬과 같은 경우 두 가지 경우 !!

 

* for ~ else 구문은, for문이 중간에 break 등으로 끊기지 않고 끝까지 수행되었을 때 else문이 수행되도록 해준다.

def solution(skill,skill_tree):
    answer=0
    for i in skill_tree:
        skil_list=''
        for z in i:
            if z in skill:
                skil_list+=z
        if skil_list==skill[0:len(skil_list)]:
            answer+=1
    return answer

각각의 스킬트리의 스킬이 스킬목록에 들어있는 경우에만 새로운 스킬 목록에 추가하고, 이를 기존의 스킬 목록과 비교하여 동일한 경우에 카운트한다. 스킬트리의 각 스킬이 스킬 목록에 들어있지 않은 경우에도 비어있는 리스트와 비교할 수 있기 때문에, 카운트 할 수 있음 !