프로그래머스[JS] > 순위

🔥문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

 

🔥후기

한참 고민하다 풀지를 못해 다른 사람들의 풀이를 참고한 뒤 문제를 풀었다. 

다른사람들의 풀이법을 참고하다 플로이드 와샬 이라는 알고리즘을 알게 되었고 내가 푼 문제의 방식은 플로이드 와샬 알고리즘을 활용한 풀이라는 점을 언급한다. 자세한 풀이법은 하단 주석을 참고하자

function solution(n, results) {

    let answer = 0;
    // n은 1부터 이므로 일부러 index 0은 신경안쓰기 위해 n+1 길이의 배열 생성
    let graph = Array.from({length:n+1},()=>Array(n+1).fill(false))
    
    // 승패 판별 가능 check
    for([win,lose] of results){
        graph[win][lose]=true
    }
    
    // [1,5], [5,6] 와 같은 경우 -> 하단 과정에서 [1,6]임을 알 수 있음
    for(let i=1; i<=n; ++i){
        for(let j=1; j<=n; ++j){
            if(graph[i][j]||graph[j][i]){
                
            }else{
                for(let k=1; k<=n; ++k){
                    if(graph[i][k] && graph[k][j]){
                        graph[i][j]=true
                        break;
                    }else if(graph[j][k] && graph[k][i]){
                        graph[j][i]=true
                        break;
                    }
                }    
            }
        }
    }
    
    
    // 총 n 명의 선수가 있을 때 1번 선수는 n-1명의 선수와의 싸움 예측이 가능하면 그 선수는 정확한
    // 순위를 알 수 있음
    for(let i=1; i<=n; ++i){
        let count = 0 ;
        for(let j=1; j<=n; ++j){
            if(graph[i][j]||graph[j][i]){
                ++count
            }
        }
        
        if(count ===n-1){
            ++answer
        }
    }

    
    
    
    return answer;
}