[프로그래머스] 순위

문제 정보

• 프로그래머스 문제 링크
• 난이도 : level 3

 

해결 방법

맨 처음에는 그래프를 순회하면서 순위를 매기는 방법을 생각했었는데 다른 node 로 이동할 때마다 순위를 명확히 체크할 수 있다는 보장이 없어서 각 node 하나하나 마다 순위를 확정할 수 있는지 체크하기로 했습니다. 주어진 예제를 확인해보니 순위를 확정할 수 있는 node 는 아래 그림과 같이 자신보다 순위가 위 이거나 아래인 다른 모든 node 들을 찾았을 때 였습니다. 그래서 upperVisited 라는 자신보다 상위 순위에 있는 node 목록과 lowerVisited 라는 자신보다 하위 순위에 있는 node 목록을 node 마다 각각 생성했습니다. 이 두개의 길이가 본인을 제외한 전체 노드 갯수인 n - 1 이 될 경우 순위를 확정할 수 있습니다.

 

소스 코드

 

// 순위가 확정되는 경우 : curNode 보다 상위 / 하위 node 의 개수를 모두 파악했을 때
function solution(n, results) {
    let answer = 0;
    let upperVisited = [];
    let lowerVisited = [];

    const getUpper = function(curNode){
        const upper = results.filter(el => el[1] == curNode).map(el => el[0]);
        //console.log(`curNode:${curNode} / upper:${upper}`);

        for(let idx = 0; idx < upper.length; idx++){
            if(!upperVisited.includes(upper[idx])){
                upperVisited.push(upper[idx]);
                getUpper(upper[idx]);
            }
        }
    };

    const getLower = function(curNode){
        const lower = results.filter(el => el[0] == curNode).map(el => el[1]);
        //console.log(`curNode:${curNode} / lower:${lower}`);

        for(let idx = 0; idx < lower.length; idx++){
            if(!lowerVisited.includes(lower[idx])){
                lowerVisited.push(lower[idx]);
                getLower(lower[idx]);
            }
        }
    };

    for(let idx = 0; idx < n; idx++){
        let curNode = idx + 1;
        upperVisited = [];
        lowerVisited = [];

        getUpper(curNode);
        getLower(curNode);
        
        //console.log(`curNode:${curNode}`);
        //console.log(`upperVisited:${upperVisited}`+'\n'+`lowerVisited:${lowerVisited}`);
        if(upperVisited.length + lowerVisited.length == n - 1){
            answer++;
        }
    }

    return answer;
}

 

추가 내용

각각의 node 마다 탐색을 해야하기 때문에 불필요한 연산이 있는 것 같은데 추후에 개선점을 찾을 생각입니다.

 

참고 자료

• x