[Level 2] 스킬트리

programmers.co.kr/learn/courses/30/lessons/49993#

코딩테스트 연습 - 스킬트리

---

접근

처음에 중복된 스킬은 주어지지 않는다는 것을 스킬 트리가 담겨있는 리스트 내에 중복된 스킬 트리가 없다는 것을 이해를 했다. 하지만 하나의 스킬 트리 내에 중복된 스킬이 없는 것이었다.

 

그래서 단순히 skill의 앞에서부터 비교하여 조건에 부합하는 스킬트리가 있는지 판단하였다.

 

구현

먼저 skill_trees를 탐색하면서 각각의 skill_tree를 검사한다.

스킬의 순서가 담겨있는 skill을 리스트형으로 변환하고 skill_tree를 탐색하면서 skill의 앞과 같은지 확인한다.

다르다면 break가 될 것이며 같다면 앞의 원소가 제거되어 다음 비교에 수월할 것이다.

만약 break없이 for문이 종료되었다면 answer을 증가시킨다.

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

---

다시 풀어보기

배워야하는 각각의 스킬들이 각각의 스킬트리 내에 어떤 인덱스에 있는지 find를 통해 찾고 이를 리스트에 순서대로 추가한다. 만약 해당 리스트가 오름차순으로 되어있지 않다면 불가능 한 것이다.

def isPossible(numbers):
    for i in range(1, len(numbers)):
        if numbers[i] != -1 and numbers[i-1] > numbers[i]:
            return False
        if numbers[i-1] == -1 and numbers[i] != -1:
            return False
    return True

def solution(skill, skill_trees):
    answer = 0
    
    for tree in skill_trees:
        numbers = []
        for s in skill:
            numbers.append(tree.find(s))
        if isPossible(numbers):
            answer += 1
    
    answer = answer if answer else 0
    return answer