프로그래머스 - 스킬트리 (문자열과 시뮬레이션)

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

프로그래머스

문제 이해

선행 스킬 순서가 주어질 때, 각 유저의 스킬트리가 순서를 어기지 않는지 판단하여 가능한 스킬트리 개수를 구한다.

접근 방법

스킬트리 순서를 어기지 않는지만 판단하면 된다. 

따라서 각 스킬트리에서 선행 스킬만 추출한 뒤, 주어진 순서의 접두사(prefix)인지 확인한다.

코드

function solution(skill, skill_trees) {
    let answer = 0

    for (const tree of skill_trees) {
        // 스킬트리에서 선행 스킬에 해당하는 문자만 남김
        const filtered = [...tree].filter(s => skill.includes(s)).join('')
        
        // 남은 문자열이 선행 스킬 순서의 접두사인지 확인
        if (skill.startsWith(filtered)) { 
        	answer++ 
        }
    }

    return answer
}

시간 복잡도

각 스킬트리에 대해 한 번씩 순회하므로 O(N × M)
(N: 스킬트리 개수, M: 스킬트리 문자열 길이)

정리

문자열 필터링과 접두사 검증으로 간단히 구현 가능한 시뮬레이션형 구현 문제.