Programmers / 스킬트리 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 스킬트리 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/49993

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

첫 풀이

def solution(skill, skill_trees):
    answer = 0

    for st in skill_trees:
        idx = 0
        check = ""

        for c in st:
            check = c
            if skill.find(c) >= 0 and c != skill[idx]:
                break
            elif skill.find(c) >= 0 and c == skill[idx]:
                idx += 1

        if check == st[-1]:
            answer += 1

    return answer

 

정확하게 풀었다고 생각했는데 틀렸다. 반례를 생각해보니깐

solution("CBD", ["CTD"]) 경우일 때 0이 나와야 하지만 1이 나온다. 선행 스킬 순서 마지막이 스킬 트리 원소 마지막에 있을 때 선행 스킬 순서를 안배워도 1로 반환하게 된다는 문제점을 찾았다.

 

def solution(skill, skill_trees):
    answer = 0

    for ski in skill_trees:
        s = ""
        for c in ski:
            if c in skill:
                s += c

        if skill[:len(s)] == s:
            answer += 1

    return answer

 

다른 방법을 생각해보니깐 선행 스킬을 얼마나 배웠는지가 중요하다는 사실을 알게 되었다. 그 말은 선행 스킬을 배운 길이랑 스킬트리에서 선행 스킬 배운 원소랑 같을 경우에 answer += 1 해주면 된다는 사실을 알게 되었다.

---

※ 알아야 할 것

 

파이썬 리스트에서 lis[a:b]의 기능은 lis원소 a부터 b -1까지 길이를 뽑아온다.