[JS] 스킬트리

 

 

난이도: Lv. 2

정답률: 57%

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

프로그래머스

 

 

알고리즘

1. 선행 스킬들을 각각 Set에 담는다.

2. skill_trees의 각 원소들에서 선행 스킬 목록에 없는 문자를 제거한다. 선행 스킬이 "CBD"이고, 스킬 트리가 "AECB" 이면 "CB"가 된다.

3. 2.의 결과 문자열과 선행 스킬 문자열을 2.의 경과 문자열의 길이만큼 자른 문자열이 동일하면 가능한 스킬 트리 이므로 정답을 1 증가시킨다.

 

 

코드

function solution(skill, skill_trees) {
    let answer = 0;
    const skillSet = new Set();

    for (let s of skill) { skillSet.add(s); }

    for (let skillTree of skill_trees) {
        let order = '';
        for (let skillName of skillTree) {
            if (skillSet.has(skillName)) { order += skillName; }
        }
        if (skill.substring(0, order.length) == order) { answer++; }
    }

    return answer;
}

 

 

주저리

탐색 좀 더 빨리 하라고 Set을 쓰긴 했는데 이 문제는 배열을 써도 상관없을 것 같긴 하다. 이 문제도 왜 정답률이 50%대인지 의문인 문제다. 푸는데 10분 정도 걸렸다.