프로그래머스 | 스킬트리(JavaScript)

2021년 2월 8일 Velog에 작성한 글을 옮겨온 글입니다.

프로그래머스 - 스킬트리

 

답안 1

function solution(skill, skill_trees) {
    const skill_regex = new RegExp(`[^${skill}]`, 'g');
    const skill_len = skill.length;
    return skill_trees.reduce((cnt, tree) => {
        tree = tree.replace(skill_regex, ''); // skill에 속하는 문자만 남김
        for(let i = 0, tree_len = tree.length; i < skill_len && i < tree_len; i++) {
            if (skill[i] !== tree[i]) return cnt; // 순서가 다를 경우 cnt에 +1 하지 않음
        }
        return cnt + 1; // 순서가 맞을 경우 cnt + 1
    }, 0);
}

우선 skill_regex를 만들어 skill_trees에서 선행 스킬 순서와 관련 없는 문자를 제거한 후, skill과 tree 내의 문자 순서를 비교하여 같은 경우에는 가능한 스킬 트리의 수(cnt)를 1 증가 시켰습니다.

 

답안 2

function solution(skill, skill_trees) {
    const skill_regex = new RegExp(`[^${skill}]`, 'g');
    return skill_trees.reduce((cnt, tree) => {
        tree = tree.replace(skill_regex, ''); // skill에 속하는 문자만 남김
        return cnt + (skill.indexOf(tree) ? 0 : 1); // indexOf
    }, 0);
}

function solution(skill, skill_trees) {
    const skill_regex = new RegExp(`[^${skill}]`, 'g');
    return skill_trees.reduce((cnt, tree) => {
        tree = tree.replace(skill_regex, ''); // skill에 속하는 문자만 남김
        return cnt + (skill.startsWith(tree) ? 1 : 0); // startsWith
    }, 0);
}

다른 분의 풀이를 보고 답안 1에서 중간에 for문으로 비교했던 부분을 함수로 변경했습니다. 동일한 코드에 indexOf와 startsWith를 적용해보았습니다.

 

indexOf performance

startsWith performance

시작점 비교로 사용하는 경우, indexOf보다 startsWith가 (용도도 적절하고) 좀 더 좋은 성능을 내는 것 같습니다.[참고]

답안 3

function solution(skill, skill_trees) {
    const skill_regex = new RegExp(`[^${skill}]`, 'g');
    return skill_trees.map(tree => tree.replace(skill_regex, ''))
      	.filter(tree => skill.indexOf(tree))
      	.length; // indexOf
}

function solution(skill, skill_trees) {
    const skill_regex = new RegExp(`[^${skill}]`, 'g');
    return skill_trees.map(tree => tree.replace(skill_regex, ''))
        .filter(tree => skill.startsWith(tree))
        .length; // startsWith
}

map과 filter로 2번 돌리는 것보다는 reduce로 한 번에 다 처리하는 것이 더 빠르지 않을까 싶어서 처음에 reduce로 접근했었는데, 같은 O(n)이여서인지 그닥 차이는 없는 것 같습니다.

 

indexOf performance

startsWith performance