프로그래머스 스킬트리 코드 및 해설 (파이썬)

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

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

 

💡 skill에서 순서가 정해진 스킬을 제외한 스킬들은 valid 여부에 영향을 주지 않습니다. 따라서 이러한 스킬들은 지운 상태에서 valid 여부를 확인하고자 합니다.

 

주어진 skill에서 가능한 순서를 모두 구해 valid에 저장합니다.

• ex) skill = "CBD"인 경우, valid = ['', 'C', 'CB', 'CBD']
  • 빈 스트링의 경우 skill에 주어진 스킬 중에선 아무것도 배우지 않는 경우를 의미함

각 skill_tree에 대해 skill에 포함되지 않은 스킬은 모두 지운 상태가 valid에 포함되는지 확인합니다. 포함되면 answer를 1씩 증가시킵니다.

• ex) skill_tree = "BACDE"인 경우, skill에 포함되지 않은 스킬을 모두 지운 상태는 "BCD"이고, 이 "BCD"가 valid 안에 있지 않으므로 answer는 증가하지 않음

 

• 시간 복잡도: O(NM)

 

def solution(skill, skill_trees):
    answer = 0
    
    # 주어진 skill에서 가능한 순서 
    # ex) skill = "CBD"인 경우, valid = ['', 'C', 'CB', 'CBD']
    valid = [skill]
    for i in range(len(skill)):
        valid.append(skill[:i])
    
    # 각 skill_tree에 대해 
    for skill_tree in skill_trees:
    	# 주어진 skill에 포함되지 않은 스킬은 지운 상태가 valid에 포함되는지 확인 
    	# ex) skill_tree = "BACDE"인 경우, "BCD"가 valid 안에 있지 않으므로 answer는 증가하지 않음 
        if ''.join([s for s in skill_tree if s in skill]) in valid:
            answer += 1
            
    return answer