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

스킬트리

문제설명

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

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

제한사항

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

풀이

이전 스킬이 완료됐다면 그 전 스킬도 완료됐다는 뜻이므로 바로 전 스킬만 확인하면 된다.

각 스킬트리마다 checked 배열을 놓고 한 글자씩 확인하면서 선행 스킬 0번이거나 이전 선행 스킬이 완료되었으면 해당 스킬을 checked 배열에 넣는다.

아니라면 불가능한 스킬 트리이므로 for문을 탈출한다.

탈출 없이 for문이 완료된다면 가능한 스킬트리이므로 +1을 한다.

def solution(skill, skill_trees):
    answer = 0
    
    for skill_tree in skill_trees:
        checked = []
        for s in skill_tree:
            if s in skill:
                idx = skill.index(s)
                if idx == 0 or skill[idx - 1] in checked:
                    checked.append(s)
                else:
                    break
        else:
            answer += 1
    return answer

개선

스킬트리는 어차피 순서대로 수행되어야한다. 스킬트리를 디큐로 만들어서 앞에서부터 꺼내면서 현재 차례가 맞는지 확인한다.

from collections import deque
def solution(skill, skill_trees):
    answer = 0
    
    for skill_tree in skill_trees:
        skill_list = deque(skill)
        for s in skill_tree:
            if s in skill_list and s != skill_list.popleft():
                break
        else:
            answer += 1
    return answer

다른 사람 풀이

각 스킬 트리에서 스킬에 해당하는 글자만 한 글자씩 붙여서 문자열을 만들고 해당 길이만큼 skill과 비교해서 같은지 확인한다.

def solution(skill,skill_tree):
    answer=0
    for i in skill_tree:
        skillist=''
        for z in i:
            if z in skill:
                skillist+=z
        if skillist==skill[0:len(skillist)]:
            answer+=1
    return answer