[Algorithm] 프로그래머스 49993 : 스킬트리

문제 접근

예전에 자료구조 시간에 배웠단 topological sort?가 생각나는 문제였다. 그 때도 위상정렬 배우면서 컴공들이 배우는 과목이 스킬 트리처럼 순서가 정해졌있다는 예시를 들었었는데ㅋㅋㅋ

아무튼 문제는 오랜만에 간단하게 풀었다.

접근 방법은 이렇다.

1. 스킬트리의 배열을 돌면서 각 스킬트리의 순서를 명시한다.
2. 이 때, 순서를 명시한다는 말은 skill 문자열에 들어간 순서를 의미한다.
3. Array의 indexOf 매서드는 만약 없다면 -1을 return 하므로
4. skill에 명시되지 않은 것들은 모두 탈락 시켜서
5. 남은 스킬들과 skill의 순서를 비교한다

다음은 내가 짠 코드다

내 코드

function check (skill, char){
    return (skill.indexOf(char)); 
} // char이 skill에서 몇 번째 index인지 return

function solution(skill, skill_trees) {
    let answer = 0;
    // skill : 선행 스킬 순서
    // skill_trees : 유저들이 만든 스킬트리
    // 가능한 스킬트리 개수를 return
    
    console.log(skill, skill_trees)
    
    // 각 스킬트리의 순서를 명시
    for(let i = 0; i < skill_trees.length; i++){
        let order = [];
        let skill_tree = skill_trees[i];
        for(let j = 0; j < skill_tree.length; j++){
            if (check(skill,skill_tree[j]) >= 0) order.push(check(skill, skill_tree[j])) 
        }
        console.log(order); // skill에 들어있는 스킬들만 골라서!!! 👍
        
        let isOk = true; // true로 해두었다가
        for(let x = 0; x < order.length; x++){
            console.log(order[x], "x",x)
            if(order[x] !== x) { // 순서랑 다르면 false
                isOk = false;
                break;
            }
        }
        if (isOk) answer ++;
     
    }
    

    return answer;
}

다른 해답

function solution(skill, skill_trees) {
    var answer = 0;
    var regex = new RegExp(`[^${skill}]`, 'g');

    return skill_trees
        .map((x) => x.replace(regex, ''))
  		// BCD BC 등이 남게되는데
        .filter((x) => {
      		// Skill BCD와 BCD, BC 등을 비교해서 완전히 같은 것만 골라냄
            return skill.indexOf(x) === 0 || x === "";
        })
        .length
}

되게 간단하게 풀으셨는데 접근방식은 같다.