프로그래머스 [Lv. 2] 스킬 트리 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

def solution(skill, skill_trees):
    answer = 0
    lenSK = len(skill)
    
    visited = [0 for _ in range(26)]
    for s in skill:
        visited[ord(s)-65] = 1

    def isValid(st):
        idx = 0
        for s in st:
            cv = skill[idx]
            if visited[ord(s)-65] and cv != s:
                return False
            if cv == s:
                idx += 1
            if idx == lenSK:
                return True
        return True
    
    for st in skill_trees:
        if isValid(st):
            answer += 1
                
    return answer

풀이 방법

1. 스킬 트리를 순회하면서 유효한지 확인한다.
2. 유효한 경우 answer를 1 더해준다.
   1. 유효한지 확인하는 방법
      1. skill을 visited에 기록한다.
         1. 예 A의 아스키 코드는 65이므로 0번째 인덱스에 1을 넣는다.
      2. skill_trees의 st의 첫 번째 원소부터 확인한다.
         1. 해당 원소가 visited에 있는 경우
            1. skill의 해당 idx의 값과 일치해야 한다.
               1. 일치 하지 않으면 스킬이 꼬였다고 판단하고 유효하지 않다를 return 한다.
         2. 걸러지지 않거나 idx가 skill의 길이만큼 되었다면 True를 반환한다.
3. 계산이 끝난 answer를 반환한다.

느낀점

• 스킬트리가 중복되는 경우였다면 (AABBCC) 어려웠을 텐데 중복이 안된다는 점이 쉬웠다.
• 하지만 주의할 점은 ABC라는 스킬이 있다면 DKAB도 유효하다는 점이다.
• 또한 문제가 더 어려웠다면 ABC라는 스킬에 AC도 유효하다고 했을 것이다.