[프로그래머스]LV. 2 - 스킬트리(Python)

[프로그래머스]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. 일단 skill_trees의 각각의 원소에 접근하는 방법을 생각했다.

• split()로 원소를 분리하는 방법도 있지만 어차피 모든 원소를 탐색해야 하기 때문에 for 문을 선택했다.

2. 처음에는 skill_trees의 원소에 skill이 그대로 포함되어 있으면 가능한 스킬트리인 줄 알고 코드를 작성했는데, 문제를 다시 읽어보니 그게 아니었다.

• 테스트 케이스 1번을 보면, skill_trees의 각 원소에 skill의 각 문자열인 "C", "B", "D"가 순서대로 들어가기만 하면 문제였다. 단순하게 "C"보다 "B"가, "C", "B"보다 "D"의 인덱스 번호가 크기만 하면 되는 문제였던 것이다.

3. 스택으로 활용할 빈 문자열 string을 선언하고, 이중 for문을 통해 skill_trees 원소의 각 문자에 접근해 skill의 각 문자에 해당되는 문자가 있다면 string에 하나씩 추가해주는 것으로 코드를 작성했다.

• 처음 for문에서 string을 빈 문자열로 초기화하는 방법을 택했다.

4. 문제에서 스킬이 중복해 주어지지 않는다는 것을 보고, string과 skill을 비교해야겠다는 생각이 들었다.

• string이 skill과 다른 순서라면 불가능, 같은 순서라면 가능한 스킬트리라고 판단하기 위해 if문을 사용했다. skill을 string의 길이만큼 슬라이싱해 skill_trees의 원소에서 사용된 문자만 비교하는 방법을 택했다.

코드

def solution(skill, skill_trees):
    answer = 0
    for i in skill_trees:
        string = ""                      
        for j in i:
            if j in skill:         
                string += j
        if skill[:len(string)] == string:    
            answer += 1
    return answer

후기

처음에 문제를 잘못 이해해서 생각보다 시간이 많이 걸린 문제였다.
문제를 다시 읽고 어떻게 풀어야될지 방향이 잡혔고, 그 뒤로 문제를 해결하는 데 많은 시간이 소요되지는 않았다.
하지만 이중 for문을 통해 skill_trees에 포함되어 있는 모든 문자를 하나씩 탐색해야 하는 방법을 택했기 때문에 시간복잡도가 매우 불량한 풀이라고 생각한다. 이 문제는 다른 방법을 사용해 다시 풀어봐야겠다. 앞으로 문제를 더 신중하게 읽어봐야 한다는 다짐도 할 수 있었다!