스킬트리 문제

이번에는 순서규칙을 맞춘 경우만 선택하는 스킬트리 문제입니다.

programmers.co.kr/learn/courses/30/lessons/49993?language=python3

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

 

바람의 나라를 예로 들어봅시다.

 

스킬트리 문제의 OK/Fail Case

 

화염주, 화열참주, 진화열참주, 극진화열참주 가 있다고 해보겠습니다.

 

이름부터 화염주<화열참주<진화열참주<극진화열참주 순의 기술인 것을 알 수 있습니다.

 

그렇다면, 화염주 -> 저주 -> 중독 -> 화열참주 를 배우는 것은 문제가 되지 않습니다.

(이때 화염주 계열 이외에는 기술의 순서가 없다고 생각합니다)

 

하지만 화열참주 -> 저주 -> 중독 -> 진화열참주 순으로는?

 

앞에 화염주는 배우기 전이기 때문에 불가능한 스킬트가 됩니다.

 

이러한 방법으로, 불가능한 경우의수를 정리하면

1. 상위 기술이 하위기술보다 먼저 배우는 경우

2. 상위 기술이 하위기술 없이 배우는 경우

 

위 두가지만 Code로 구현 해 준 후 각 스킬트리를 점검해주면

 

유효한 스킬트리 여부를 확인할 수가 있게됩니다 :)

 

아래는 Python으로 구현한 해당 문제의 해 입니다.

def solution(skill, skill_trees):
    answer = 0
    #정해진 스킬트리의 순서인 skill을 list화
    skill = list(skill)
    #체크한 skill tree마다 순서가 정해진 skill의 위치를 파악하기 위한 temp_list
    temp_list = [[None for j in range(len(skill))] for i in range(len(skill_trees))]
    #각 skill tree의 값 중 skill에 해당하는 값이 있는지를 확인 후
    #값이 있을경우 해당 값의 위치를 기록
    for i in range(len(skill)):
        for j in range(len(skill_trees)):
            for k in range(len(skill_trees[j])):
                if skill_trees[j][k] == skill[i]:
                    temp_list[j][i] = k
    
    #해당 skill_tree가 유효한지 여부를 기록할 변수를 선언합니다
    validation = True
    #각 skill_tree마다 산출한 temp_list를 기반으로
    #해당 skill_tree가 유효한지 판단합니다.
    for i in range(len(temp_list)):
        for j in range(len(temp_list[i])-1):      
        	#검사중인 skill_tree에서 현재검새원소와 다음 원소가 모두 있는경우            
            if temp_list[i][j]!=None and temp_list[i][j+1]!=None:
            	#이 경우 낮은 스킬보다 높은 스킬을 먼저 배웠으므로 무효
                if temp_list[i][j]>temp_list[i][j+1]:
                    validation = False
                    break
            #이 경우 판단할 근거가 없으므로 pass
            elif temp_list[i][j]!=None and temp_list[i][j+1]==None:
                pass
            #이전 스킬을 배우지 않았는데 다음 스킬을 배웠으므로 무효
            elif temp_list[i][j]==None and temp_list[i][j+1]!=None:
                validation = False
                break       
        #유효성 판단이 True일 경우 유효한 스킬트리의 개수를 하나 추가
        if validation:
            answer +=1
        validation = True
    return answer
solution("CBD", ["BACDE", "CBADF", "AECB", "BDA"])
==> 2