[Javascript] 스킬트리 (49993)

문제링크

코딩테스트 연습 - 스킬트리

 

 

접근 방법

나의 풀이 

조건별로 나누어 코드를 구현하였다.
1. skillTree의 배열이 선행 스킬을 포함할때 (skillTree.includes(skill[i-1])
1. 1 skillTree에서 선행 스킬보다 다음 스킬의 index번호가 크거나 다음 스킬이 없을 때
=> isRightSkillTree = true;
1. 2 skillTree에서 선행 스킬보다 다음 스킬의 index 번호가 작고 다음 스킬이 있을 때
=> isRightSkillTree = false;

2. skillTree의 배열이 선행 스킬을 포함하지 않을 때
2. 1 선행스킬은 포함하지 않는데, 다음 스킬은 포함할 경우
=> isRightSkillTree = false;
2. 2 skill의 모든 스킬을 포함하지 않는 경우 (순서가 없는 스킬들로만 이뤄져 있음)
=> isRightSkillTree = true;

하지만 이러한 접근이 어디가 잘못됐는지.. 테스트 케이스 14번만 통과하지 못했다.

그런데 예외 케이스를 찾다가 더 좋은 풀이를 발견하였다.

아이디어 : 스킬트리에서 순서가 없는 스킬들은 고려할 필요가 없다.

filter 메서드를 통해 skill_trees에 skill에 있는 스킬만 추출하여 순서를 파악하면 된다.

 

 

// 더 좋은 풀이

function solution(skill, skill_trees) {
    var answer = 0;
    const orderSkillTree = new Array(skill_trees.length).fill("");
    
    // skill_trees의 elements 중 skill에 포함되는 elements만 찾는다.
    skill_trees.filter((skillTree,idx) => {
      for(let i = 0; i < skillTree.length; i++){
        if(skill.includes(skillTree[i])) orderSkillTree[idx] += skillTree[i]
      }
    })
    
    // 찾은 orderSkillTree와 skill의 orderSkillTree의 길이 만큼 자른 substr이 같다면 +1을 한다.
    orderSkillTree.forEach(skillTree => {
        if(skillTree === skill.substring(0, skillTree.length)) answer += 1;
    })
    
    return answer;
}

 

 

// 나의 풀이

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

    skill_trees.forEach(skillTree => {
        for(let i = 1; i < skill.length; i++){
            // 이전 스킬이 있을때
            if(skillTree.includes(skill[i-1])){
                //이전 스킬보다 다음 스킬의 index번호가 크거나 다음 스킬이 없을때
                if(skillTree.indexOf(skill[i-1]) < skillTree.indexOf(skill[i]) || skillTree.indexOf(skill[i]) === -1){
                    isRightSkillTree = true;
                }
                // 이전 스킬보다 다음 스킬의 index번호가 작고 다음 스킬이 있을때 
                else {
                    isRightSkillTree = false;
                    break;
                }
            }else{
                // 이전스킬은 없는데 다음 스킬은 있을때 
                if(skillTree.includes(skill[i])){
                    isRightSkillTree = false;
                    break;
                }
                // skill과 겹치는 스킬이 없을때 (순서가 상관없는 스킬들만 존재)
                isRightSkillTree = true;
            }
        }
        if(isRightSkillTree) answer += 1;
    })
    
    return answer;
}