[프로그래머스] Lv2. 순위 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 택배상자

문제

제한사항

📌 내가 생각한 풀이

n명이 있는 경기에서, n-1번 경기를 하면, 순위가 반드시 정해진다! 즉 이긴횟수 + 진횟수를 더한 값이 n-1이면 된다. 또한 a->b 이고 b->c이면 a->c이다가 성립됨을 이용하여, 1~n번까지 자신이 이긴 사람과 진사람의 수를 구하자.

// 이긴횟수 + 진횟수 === n-1이면 순위 픽스


function solution(n, results) {
    var answer = 0;
    let graph = {};
    for(var i = 1; i<=n; i++){
        graph[i] = []
    }
    results.forEach((data)=>{
        let [w,l] = data
        graph[w].push(l);
    })
    
    let count = {};
    
    for(var i = 1; i<=n; i++){
        let start = i;
        let visited = [start];
        let needVisit = graph[start];
        while(needVisit.length !== 0){
            let shifted = needVisit.shift();
            if(!visited.includes(shifted)){
                visited.push(shifted);
                needVisit.push(...graph[shifted])
            }
        }
        visited.forEach((d)=>{
            if(count[d] === undefined){
                count[d] = 1
            }else{
                count[d]++
            }
        })
        graph[start] = visited
    }
    for(var i = 1; i<=n; i++){
        if(graph[i].length + count[i] === n+1){
            answer++;
        }
    }
    return answer
    
}

📌 느낀점

다른 사람들의 풀이를 보니 2차원 배열을 사용하여, 이기는 사람의 경기수를 표시해주었고, 한번의 for문을 더 돌아서 총 경기의 수를 구하였다. 플로이드 와샬 알고리즘 유형이므로, 플로이드 와샬 알고리즘 공부를 추가적으로 더 하겠다.