[코테] 프로그래머스 파이썬 Lv2. 스킬트리

선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

 

코딩테스트 연습 - 스킬트리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

 

우선 딕셔너리를 통해 문자열을 숫자로 바꾸어 진행하고자 하였다. skill에 해당하는 알파벳은 숫서대로 1,2,3,..의 값을 가질 수 있도록 하였고 나머지 값들은 ' '으로 두었다. 이를 통해 skill_trees를 순회할 때, 선행스킬이 필요한 것들만 남길 수 있도록 하였다. 

 

이후에는 collections 라이브러리의 OrderedDict을 통해서 문자열의 순서는 유지하되, 중복은 사라질 수 있도록하였다. 이를 통해 각 선행 스킬 중 가장 앞쪽에 오는 것만 솎아낼 수 있도록 하였다. 남아있는 문자열의 길이를 활용해서 skill의 앞부분만 slice한 뒤, 이에 해당한다면 가능한 스킬트리로 해두었다.

 

라이브러리를 사용하지 않고 솎아내려면 stack에 하나씩 넣고, 스택 안에 동일한 값이 있다면 넣지 않는 방법도 가능할 것 같다.

 

from collections import OrderedDict

def solution(skill, skill_trees):
    answer = 0
    cnt=1
    dicts={}
    check=ord("A")
    result=[]
    finalSkill=''
    
    for i in range(check, check+26):
        dicts[chr(i)]=""
        
    for i in skill:
        dicts[i]=str(cnt)
        finalSkill+=str(cnt)
        cnt+=1
    
    for i in skill_trees:
        strs=i
        for j in i:
            strs=strs.replace(j,dicts[j])
        result.append(strs)
    
    for i in result:
        unique_chars = ''.join(OrderedDict.fromkeys(i))
        if unique_chars in finalSkill[:len(unique_chars)]:
            answer+=1
            
    return answer