[프로그래머스] 스킬트리 (Javascript)

문제

[프로그래머스] 스킬트리

풀이

문제 정의

선행 스킬이란 어떤 특정 스킬을 배우기 위해 배워야 하는 스킬이다. skill = "ABC"가 주어졌을 때, C의 선행스킬을 B이고, B의 선행스킬은 A이다. 따라서 "B->A->C"와 같은 스킬트리는 불가능하다. 하지만 skill에 포함되지 않은 다른 스킬들은 중간에 포함되어도 상관없다. 예를 들어 "A->G->B" 는 가능한 스킬트리다.
skill과 여러 개의 스킬트리가 주어졌을 때, 가능한 스킬트리의 개수를 구하자.

해결방안

각각의 스킬트리를 전부 검사해야 한다.
skill = "CBA", skill_trees[0] = "BACDE" 일때를 가정해보자.
스킬트리의 첫 번째 스킬('B')은 skill에 포함되어 있는 스킬이므로 skill의 순서를 따라야 한다.
만약 포함되어 있지 않은 스킬을 만난다면 언제 배우든 상관 없는 스킬이기 때문에 그냥 무시하고 넘어간다.

현재 배워야할 스킬은 skillIdx라는 변수에 저장하도록 해주고 0으로 초기화한다.
skill[skillIdx] === 'C'이기 때문에 'B'는 아직 배울 수 없다. 따라서 현재의 스킬트리는 불가능한 스킬트리이기 때문에 다음 스킬트리로 넘어간다.
만약 배울 수 있는 스킬이라면 skillIdx를 1 증가시키고 계속해서 확인하면 된다.

코드 1

function solution(skill, skill_trees) {
    let answer = 0;
    for(let i=0; i<skill_trees.length; i++){
        let skillIdx = 0;
        let valid = true;
        for(let j=0; j<skill_trees[i].length; j++){
            if(skill.includes(skill_trees[i][j])){
                if(skill_trees[i][j] === skill[skillIdx]) skillIdx++;
                else {
                    valid = false;
                    break;
                }
            }
        }
        if(valid) answer++;
    }
    return answer;
}

// 첫 번째 스킬트리(문자열)부터 검사한다. (i는 0 ~ skill_trees.length-1)
//	스킬트리의 첫 번째 스킬(문자)부터 검사한다.  (j는 0 ~ skill_trees[i].length-1)
//    	j 번째 스킬이 skill에 포함되어 있는가?
//		(네) skill인덱스가 가리키고 있는곳의 문자인가?
//    		(네) skill인덱스를 1 증가시킨다. (예를 들면, "CBD"의 "C"를 가리키고 있던 인덱스가 "B"를 가리키도록)
//    		(아니오) skill 인덱스를 0으로 초기화하고, 다음 문자열로 넘어간다.
//		(아니오) j를 1증가시킨다.
//	모든 문자를 검사했는가?
//	(네) answer++

코드 2 (정규표현식 사용)

function solution(skill, skill_trees) {
    const regexp = new RegExp(`[^${skill}]`,'g'); // skill에 포함되지 않은 스킬
    skill_trees = skill_trees.map(e=>e.replaceAll(regexp,''));
    return skill_trees.filter((x)=> skill.indexOf(x) === 0).length;
}

정규표현식을 사용해서 skill에 포함되어 있지 않은 스킬들은 언제 배우든 상관없으니까 skill_trees배열에서 제거해준다.
그리고 남은 스킬트리를 방문하며 순서에 맞는 스킬트리의 개수를 리턴해준다.

"CBA".indexOf("") // 0
"CBA".indexOf("C") // 0
"CBA".indexOf("CB") // 0
"CBA".indexOf("CBA") // 0

"CBA".indexOf("CAB") // -1
"CAB".indexOf("A") // 1

혹은 indexOf 대신 startsWith 메서드를 사용해도 된다.

function solution(skill, skill_trees) {
    const regexp = new RegExp(`[^${skill}]`,'g'); 
    skill_trees = skill_trees.map(e=>e.replaceAll(regexp,''));
    return skill_trees.filter((x)=> skill.startsWith(x)).length;
}