[Python 파이썬] 프로그래머스 - 스킬트리

 

2024년 6월 7일

문제 링크 : 프로그래머스 - 스킬트리

프로그래머스

 

 

---

문제 접근

 

스킬을 배우는 순서가 CBD라면, C를 배워야 B를 배우고 B를 배워야 D를 배울 수 있다.

 

딕셔너리를 선언하여 스킬을 key, 배우는 순서를 value로 지정하였다.

이게 가능한 이유는 스킬이 중복되지 않기 때문. 

 

검증해보는 스킬트리를 앞에서부터 탐색하며 딕셔너리의 배우는 순서와 비교해본다.

아직 배울 수 있는 순서가 아닌데 스킬을 배우려고 한다면 가차 없이 탐색을 종료하고, 스킬트리의 맨 마지막 스킬까지 탐색하여 유효함이 검증된다면 가능한 스킬트리 개수를 1 증가시킨다.

 

---

순서도

 

1. 선행 스킬 순서 skill과, 가능한지 검증하기 위한 스킬트리들인 skill_trees 배열을 입력받는다.

2. key : value가 스킬 : 습득 순번 형태인 딕셔너리 skill_dict를 선언하여 값을 대입한다.

3. skill_trees의 각 스킬트리를 검증한다. 선행 스킬을 배우는 순번인 seq를 선언하여 0으로 초기화해준다.
3-1. 스킬트리의 맨 앞에서부터 탐색하며, 현재 배우려는 스킬이 skill_dict에 있으면 스킬의 값이 현재 seq와 같은지 검증한다.
3-2. 만약 같다면, seq를 1 증가시키고, 다르다면 해당 스킬트리는 불가능하므로 로직을 종료한다.
3-3. 해당 스킬트리가 가능하다면 answer을 1 증가시킨다.

4. 가능한 스킬트리 개수인 answer을 return한다.

 

 

---

전체 코드

 

def solution(skill, skill_trees):
    answer = 0
    
    # 키 : 값
    # 스킬 : 순번
    skill_dict = {}

    for i in range(len(skill)):
        skill_dict[skill[i]] = i
    
    for skill_tree in skill_trees:
        seq = 0
        isValid = True

        # 순번에 맞지 않게 먼저 마스터하려는 스킬 있는지 탐색
        for i in range(len(skill_tree)):
            if skill_tree[i] in skill_dict:
                # 순번에 맞는 순서의 스킬이면 seq + 1
                if skill_dict[skill_tree[i]] == seq:
                    seq += 1
                # 아니면 불가능한 스킬트리
                else:
                    isValid = False
        if isValid:
            answer += 1

    return answer

if __name__ == "__main__":
    skill = "CBD"
    skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]
    
    print(solution(skill, skill_trees))

---

풀이 후기

 

딕셔너리를 통해 시간복잡도 면으로 이점을 챙기려고 시도했다.