[프로그래머스] '스킬트리' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

 

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

 

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

 

 

 

 

제한사항

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 CBD로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

 

입출력 예

skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

알고리즘 분석

 

• 나의 풀이

import re
def solution(skill, skill_trees):
    answer = 0
    tmp_skill = '[' + skill + ']' # 정규표현식을 compile할 때 사용할 tmp_tree
    tree_len = len(skill_trees) # skill_trees의 길이 
    p = re.compile(f'{tmp_skill}') # tmp_tree를 이용해 컴파일 
    for i in range(tree_len): # skill_trees의 길이만큼 반복 
    	# 정규표현식을 이용해서 skill에 있는 문자들을 제외한 문자를 뺀 문자열을 반환 
        tree = ''.join(p.findall(skill_trees[i])) 
        for x, y in zip(skill, tree): # skill과 tree의 요소를 하나씩 불러옴 
            if x != y: break # 두 요소의 값이 다를 경우 반복물 탈출
        else: answer += 1 
    return answer

 

skill에 있는 알파벳 문자들을 제외한 알파벳 문자는 필요하지 않기 때문에 정규표현식으로 지워버렸다.  

그 결과를 tree에 저장하고 그저 비교만하면 되기에 큰 어려움은 없는 문제이다. 

단지, 정규표현식을 사용해본적이 없을 경우 많이 복잡할 수 있다. 

 

 

• Most1의 풀이

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees: 
        skill_list = list(skill) # skill을 list로 변환 

        for s in skills: # skills의 요소를 하나씩 불러들이며 반복 
            if s in skill: # s가 skill안에 있을 경우 
                if s != skill_list.pop(0): # s와 skill_list를 pop한 값이 같을 경우 
                    break
        else:
            answer += 1

    return answer