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

문제

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 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예
skill skill_trees return
"CBD" ["BACDE", "CBADF", "AECB", "BDA"] 2

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

---

풀이

def solution(skill, skill_trees):
    answer = 0
    
    for i in range(0,len(skill_trees),1):
        skill_trees[i] = ''.join(c for c in skill_trees[i] if c in skill)

    for k in skill_trees:
        if k == skill[0:len(k)] :
            answer +=1

    return answer

 

---

설명

- 알고리즘 접근 불가능

- 그래도 그 중에서 내가 가장 이해할 수 있다고 생각해서 적는다.

 

<알고리즘 설명>

- skill 에 주어진 스킬 순서가 중요!

그래서 skill에 주어지지 않은 다른 스킬들은 순서에 상관없이 배울 수 있기 때문에 문제를 풀 때 skill에 주어지지 않은 스킬들은 제거하고 시작을 했다.

- 처음 for문을 보면 join문을 이용했는데, join는 리스트를 특정 문자열을 포함해 문자열로 반환해주는 함수이다. join문을 보면 먼저 skill_tress에서 하나씩 스킬 트리를 뺀다. 예시로 "BACDE"를 보자면 "BACDE"에서 for 문을 통해 순서대로 "B", "A", "C", "D", "E"가 c가 된다. 그래서 만약 c가 skill인 "CBD" 중에 한 알파벳이라면 문자열에 들어가는 것이다. 저 join문을 통해 "BACDE"는 "BCD"가 된다.

이제 주어지지 않은 스킬들을 다 제거했다면 그들만을 가지고 다시 for문을 돌린다.

- 두번째 for문에서는 선행 스킬이 잘 이뤄지고 있는지를 판단하는 것이다. 이제 남은 알파벳들은 모두 skill에 있는 알파벳이니깐 순서만 판단하면 된다. 현재 "BACDE"는 제거를 통해 "BCD"가 되었는데, B는 C를 먼저 배운 다음에 쓸 수 있는 스킬이기 때문에 틀린 스킬 트리가 돼야 한다. 그래서 skill을 슬라이싱을 이용해 같은 길이로 잘라주었다. 여기서 중요한 점은 슬라이싱을 0에서부터 시작하는 것이다. 선행을 해야 하기 때문에 꼭 0부터 시작하는 게 중요하다. 그래서 만약 같은 길이로 만들었을 때, 두 개가 같다면 가능한 스킬 트리가 되는 것이다.

 

<추가 설명>

1. join

- join()을 이용하면 다음과 같이 리스트를 문자열로 변환할 수 있습니다.

char.join(s for s in list) 는 리스트의 모든 요소들 간에 char로 연결하여 하나의 문자열로 리턴

str_list = ['This', 'is', 'a', 'python tutorial']
result = ' '.join(s for s in str_list)
print(result)

Output:

This is a python tutorial

 

2. range

- range(<시작값>, <종료값>, <증분>)

 

ex) 홀수 출력하기

for odd in range(1, 10, 2):
    print(odd, end=' ')

결과:

1 3 5 7 9