[프로그래머스] Lv.2 스킬트리(python)

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

프로그래머스

 

문제 설명

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

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

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

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

제한 조건

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

 

문제 해결 & 각 문제 풀이 설명

1. 첫 번째 방법

def solution(skill, skill_trees):
    answer = 0
    arr = [[] for _ in range(len(skill_trees))]
    for i in range(len(skill_trees)):
        for j in range(len(skill_trees[i])):
            if skill_trees[i][j] in skill:
                arr[i].append(skill.index(skill_trees[i][j]))
    print(arr)
    for i in arr:
        flag = 1
        index = 0
        for j in i:
            if j != index:
                flag = 0
                break
            index += 1
        if flag:
            answer += 1
    return answer

먼저 skill_trees에 있는 불필요한 문자열을 제외시키고, 필요한 문자는 skill의 index 값을 집어넣어줬다.

그러면 arr 리스트에는 각 문자의 인덱스 값만이 들어가게 되는데, 이때 0, 1, 2 .... 이렇게 차근차근 증가하지 않는다면 불가능한 스킬트리라는 것을 알 수 있다. 따라서 두번째 for문을 돌며 올바른 스킬트리의 갯수를 세어준 다음 return 하면 해결이다.

하지만 문제풀이가 너무 길어진 느낌이 들어 다른 해결방법을 가져왔다.

 

2. 두 번째 방법

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

가독성도 좋고 이해하기 쉬운 코드를 발견해 다른사람의 풀이를 가져와봤다.

먼저 필요한 문자만을 저장하는 skillist 문자열을 만들고, 한번 돌고 난 이후에 만약 스킬트리의 순서와 맞다면 answer을 증가시켜주는 구조이다. skill[0:len(skillist)]로 비교하는 이유는 뒷부분 스킬은 배우지 않아도 배울수만 있으면 answer을 증가시켜줘야 하기 때문에 순서가 맞는지 확인하기위해서다.