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

https://school.programmers.co.kr/learn/courses/30/lessons/49993

프로그래머스

Level 2. 스킬트리

Summer/Winter Coding(~2018) 

 

 

접근 방식
1. 입력된 스킬을 순서대로 숫자로 치환한다.
2. 치환한 숫자를 제외한 모든 문자를 정규식을 사용하여 삭제한다.
3. skill_trees 배열을 돌면서, 숫자가 순서대로인지 확인한다.
  3-1. 길이가 0일 때(선행 스킬이 존재하지 않는 스킬)에는 넘어간다.
  3-2. 길이가 1일 때에는 무조건 가장 먼저 선행되어야 하는 스킬(숫자는 0)이 아닐 경우 +1 한다.
  3-3. 위의 경우가 아니며, 가장 먼저 선행되어야 하는 스킬이 존재하지 않을 때 +1 한다.
  3-4. 위의 경우가 모두 아닌 경우
    3-4-1. 문자열을 정렬하고 본래 문자열과 비교하여 일치하지 않다면 +1한다.
    3-4-2. 위의 경우가 아닌 경우는, 중간숫자가 없을 때의 경우로 해당 경우를 확인한다.
4. 스킬트리 배열의 길이에서 가능하지 않은 경우를 뺀 값을 return 한다.

 

 

코드

def solution(skill, skill_trees) :
    answer = 0
    
    # c = 1, b = 2, d = 3으로 치환한다.
    for i in range(len(skill_trees)):
        
        for s in skill:
            if skill_trees[i].find(s) != -1:
                tree = skill_trees[i]
                
                idx = str(skill.find(s))
                tmp = tree.replace(s, idx)
                loc = skill_trees.index(tree)
                
                skill_trees[loc] = tmp
        
    # 숫자를 제외한 모든 문자를 삭제함    
    for tree in skill_trees :
        loc = skill_trees.index(tree)
        
        #정규식 사용
        skill_trees[loc] = re.sub(r'[^0-9]', '', tree)
    # print(skill_trees)
    
    # 배열을 돌면서, 
    for tree in skill_trees:
        # if #공백이면 해당 문자 넘어가기
        if len(tree) == 0 :
            continue
        
        elif len(tree) == 1:
            if tree != '0' :
                answer += 1
                
        elif '0' not in tree :
            answer +=1
            
        elif len(tree) >=2 :
            n_sort = sorted(tree, reverse = False)
            n = str("".join(n_sort))
            
            if tree!=n:
                answer+=1
                continue
            
            #중간 숫자 없는 경우
            for i in range(len(tree)) :
                if str(i) not in n :
                    
                    if int(max(tree)) > i :
                        answer+=1
                        
    
    return len(skill_trees) - answer

 

 

다 풀고 나니까.. 다이나믹인가?.. 싶기도 하고 구현인 것 같기도 하고.. 

경우의 수를 다 확인하는 게 좀 쉽지 않았지만 그래도 많이 걸리지는 않았던 것 같다.

접근 방식을 써놓고 보니까 좀 기네..