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

문제

풀이

skill이라는 스킬 순서가 주어진다.

skill_trees에 있는 각 스킬트리에 대해, skill 스킬 순서를 지키고 있는지 확인하는 문제이다.

 

나는 다음과 같이 풀이했다.

 

1. dic이라는 딕셔너리를 선언한다.

이 딕셔너리에는 각 스킬에 대한 선행 스킬 정보를 저장한다.

# 딕셔너리에 각 스킬 별 선행 스킬 저장
for i in range(len(prev_skill)):
    dic[prev_skill[i]] = prev_skill[:i]

 

2. skill_trees의 각 스킬트리를 검사한다.

이때 all_exist라는 bool 값을 두었다.

 

3. 스킬 트리의 각 스킬을 검사한다.

나는 스킬트리의 맨 뒤 스킬부터 검사했다. 

 

4. 해당 스킬(skill_tree[j])을 쓰기 위해 배워야하는 선행 스킬 리스트(now_skill)와, 실제 먼저 배워진 스킬 리스트(prev_skill)을 구한다.

# 현재 스킬트리 스킬의 선행 스킬들 now_skill
now_skill = dic[skill_tree[j]]
# 현재 스킬트리 스킬이 실행되기 전 배워진 스킬들
prev_skill = skill_tree[:j+1]

 

5. now_skill의 모든 원소가 prev_skill안에 있는지 검사한다. 만약 하나라도 존재하지 않는다면 all_exist 값을 false로 바꾸어준다.

# now_skill에 있는 스킬들이 prev_skill에 전부 있으면 answer += 1
for k in now_skill:
    if k not in prev_skill:
        all_exist = False
        break

 

6. 한 스킬 트리의 각 스킬에 대해 3,4,5 과정을 반복한다.

 

7. 위 과정을 거친 후에 all_exist값이 true라면, 모든 스킬이 선행스킬 조건을 만족한 것이므로 answer에 1을 더해준다.

 

코드

def solution(skill, skill_trees):
    answer = 0
    prev_skill = list(skill)
    dic = {}

    # 딕셔너리에 각 스킬 별 선행 스킬 저장
    for i in range(len(prev_skill)):
        dic[prev_skill[i]] = prev_skill[:i]
    
    print(dic)
    
    for i in skill_trees:
        skill_tree = list(i)
        all_exist = True
        for j in range(len(skill_tree)-1,-1,-1):
            # 선행 스킬이 있는 경우만 검사    
            if skill_tree[j] in dic:
                # 현재 스킬트리 스킬의 선행 스킬들 now_skill
                now_skill = dic[skill_tree[j]]
                # 현재 스킬트리 스킬이 실행되기 전 배워진 스킬들
                prev_skill = skill_tree[:j+1]
                # now_skill에 있는 스킬들이 prev_skill에 전부 있으면 answer += 1
                for k in now_skill:
                    if k not in prev_skill:
                        all_exist = False
                        break               
        if all_exist:
            answer += 1
    return answer

 

 

프로그래머스