[프로그래머스] 스킬트리 [Summer/Winter Coding2019] [python]

[프로그래머스] 스킬트리 [Summer/Winter Coding2019] [python] Level2

 

문제 설명

 

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

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

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

선행 스킬 순서 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

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• CBADF: 가능한 스킬트리입니다.
• AECB: 가능한 스킬트리입니다.
• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

설계 및 구현

 

my_solution

def solution(skill, skill_trees):    
    #1
    answer = 0
    res = []
    
    #2
    for i in range(len(skill)):
        res.append(skill[:i+1])
    res.append("")
    
    #3
    for i in skill_trees:
        tree = ""
        for j in i:
            if j in skill:
                tree += j
        if tree in res:
            answer += 1
    #4     
    return answer

접근 방법

첫번 째로 스킬트리대로 스킬을 배울수 있는 경우를 모두 구한다.

ex) skill = "CBD"의 경우

skill의 스킬을 하나도 배우지 않을때 ""와 순서대로 "C", "CB", "CBD"로

가능한 스킬트리 = ["", "C", "CB", "CBD"]로 구할 수 있다.

그리고 skill_trees에서 skill의 요소만을 구하여 가능한 스킬트리안에 존재한다면 answer+=1을 해준다.

 

코드설명

1. 갯수를 셀 answer과 가능한 가능한 선행스킬트리를 저장할 res를 선언한다.

2. skill을 순회하며 가능한 선행스킬트리를 res에 저장한다. 선행스킬을 하나도 배우지 않을 경우 "" 도 저장한다.

3. ①skill_trees를 순회하며 skill의 값을 발견한다면 tree에 쌓아준다.

   ②가능한 선행스킬트리 res안에 tree가 있다면 가능한 스킬트리이니 answer += 1을 해준다.

4. 가능한 경우의 수 answer을 반환주어 해결  할 수 있다.

 

 

모번 solution

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

for -else구문과 stack개념을 사용하여 접근한 solution이다.

for -else구문을 사용해 본 적이 없어서 생소 했지만 구글링을 해보니

for ~ else문은 “for문에서 break가 발생하지 않았을 경우”의 동작을 else문에 적어주는 것을 알 았다.

고로 s가 skill에 있고 sklii_list[0]과 같다면 else구문의 동작을 수행한다.

ex)skill_list = ["C", "B", "D"], skills = "CBADF"의 경우

s in skill이면 skill_list[0] == s여야만 -> 선행스킬트리대로 스킬을 배워야만

answer+=1을 해준다는 것이다.

for -else구문이 익숙치 않아 구글링을 해보고 코드를 이해했다.