프로그래머스 - 스킬트리

프로그래머스 - 스킬트리

문제 접근 방법

정규 표현식을 사용해서 주어진 스킬트리와 관련없는 스킬들은 전부 지운다.
남아있는 문자열이 주어진 스킬트리 문자열에서 어느위치에 있는지 확인하다.

주어진 스킬트리가 'ACD'라고 가정하고 이것과 상관없는 모든것을 지운다.
남은 문자열의 상태 및 위치를 파악한다.
이때, 유도되는 결과는 다음과 같다.

1. 빈문자열이 남았다면, 모두 주어진 스킬트리와 관련이 없던 것으로
   어떠한 문자열이 왔더라도 정상적인 스킬트리이다.
2. 빈문자열이 아니고, 주어진 스킬트리 문자열에서의 위치가 0번째 라면,
   정상적인 스킬트리이다.
   • ex) 'ACD'에서 스킬트리에 의해 배우는 단계는 'A', 'AC', 'ACD'밖에 존재하지 않는다.
     'CD', 'AD'등의 0번째 인덱스위치에 있지 않는 문자열들은 스킬트리의 규칙에 의거하지 않는다.

이렇게 정규표현식을 거친 배열을 filter로 위 조건을 검출하고 길이를 돌려준다.

완성한 솔루션

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

    // 1. 들어온 skill_trees에서 skill을 제외하고 지운다.
    // 2. 남은 kill_trees에서 skill의 순서가 지켜지는지 확인한다.
        // 2-1. 스킬은 모두 있을 필요가 없다.
        // 2-2. 단, 존재한다면 이전 스킬을 이미 배워야 한다.

    let reg = new RegExp(`[^${skill}]`, 'g');
    let temp = skill_trees.map((val) => (val.replace(reg, ''))).filter((val) => {
        return val === '' ? true : skill.indexOf(val) === 0;
    })

    return temp.length;
}

제출하기 전에 항상 볼걸...

map과 filter를 같이 써야 할거같으면 reduce를 써라.
물론 순회가 중첩되는것은 $O(n^2)$이고
순회가 반복되는 것은 $O(2n)$ -> $O(n)$ 이기 때문에 크게 상관없겠지만
첫 순회에 끝낼 수 있는것을 다음 반복으로 돌릴 필요는 없어보인다.