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

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/49993?language=javascript

프로그래머스

 

 

 

쉽게 생각하면 skill_trees의 각 문자열의 글자별로 탐색하면서, 매번 skill을 탐색하면 될 것 같습니다. 하지만 이렇게 하면 문자열 1개당 시간복잡도가 O(N^2)이 되서 전체 O(N^3)이 됩니다.

 

특정 영역에 데이터가 있는지 없는지 판단하고 싶을 때는 Map이나 Set을 사용하는게 시간을 O(lgN)으로 줄일 수 있습니다. 하지만 비교하면서 순서도 신경써야하기 때문에 Map을 사용해서 index값을 넣어서 순서도 같이 저장했습니다.

 

 

 

 

 

function solution(skill, skill_trees) {
    var answer = 0;
    
    const m = new Map();
    for(let i = 0; i < skill.length; i++) {
        m.set(skill[i], i);
    }
    
    
    skill_trees.forEach(function(el) {
        let index = 0;
        let flag = false;
        for(let i = 0; i < el.length; i++) {
            if(m.has(el[i])) {
                if(m.get(el[i]) !== index++) {
                    flag = true;
                    break;
                }
                
            }
        }
        if(!flag) answer++;
    });
    
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~