[プログラマー]ランキング(レベル3)Javascriptプール

質問ショートカットhttps://programmers.co.kr/learn/courses/30/lessons/49191

質問する

ボクシングの試合にはn人のボクサーが参加し、それぞれ1番からn番まで参加した.ボクシングの試合は1対1で行われ、A選手の実力がB選手より優れていれば、A選手はいつもB選手に勝つ.審判は与えられた試合の結果に基づいて選手をランキングしたいと思っている.しかし、いくつかの試合結果を失ったため、正確な順位はつけられなかった.
アスリートの数n,試合結果の2次元配列結果をパラメータとして与える場合は,正確に並べ替えられるアスリートの数を返すために解関数を記述してください.

せいげんじょうけん

選手の数は1名以上100名以下.

試合の結果は1試合以上4500試合以下であった.

その結果、各行[A,B]を並べてA選手がB選手に勝ったことを示す.

すべての試合の結果に矛盾はなかった.

I/O例

nresultsreturn5[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]2

I/O例説明

2番選手は[1,3,4]選手に敗れ、5番選手が勝利したので4位だった.
5番は4位の2番に負けて5位だった

私の答え

最初は方向性のあるグラフの問題だと思いました.勝った選手から負けた選手の方向にグラフを描き、求球者のノードから始点まで乗るので、出会ったノードは始点ノードが勝つノードになります.
例を参照すると、4番ノードを始点と呼ぶと[4, 2], [2, 5]であるため、4->2->5方向にナビゲートすることができ、4番ノードは2番ノードと5番ノードに勝つことができる.
グラフを描くのは簡単ですが、ランキングの条件が何なのか思い出せません.だから他のブログを参考にして、특정 노드가 이긴 노드의 수 + 진 노드의 수 === n - 1でランキングを確定することができます.
では,この問題の鍵は勝者ノード数と敗者ノード数を求めることにある.
グラフを探索する過程で、AノードでBノードにアクセスできれば、arr[A][B]=trueノードにアクセスすることができる.これは、AノードがBノードに勝つことを意味する.
この長ノードの数はtrueであるべきで、どのように真ノードの数を求めますか?arr[A][B]がtrueならAがBに勝ったでは、Aのノードはarr[_][A]でありtrueであると考えられる.
次は私の解題方法です.

function solution(n, results) {
    var answer = 0;
  	// arr를 false로 초기화한다.
    const arr = new Array(n).fill(null).map(sub => sub = new Array(n).fill(false)); 
    
  	// arr를 완성한다.
    for(let j = 1 ; j <= n ; j += 1){
        explore(j, j, results, arr);
    }

    for(let i = 0 ; i < n ; i += 1){
        let winCnt = 0;
        let loseCnt = 0;
        
      	// i 노드 입장에서 이긴 수와 진 수를 카운트한다.
        for(let j = 0 ; j < n ; j += 1){
            if(j !== i && arr[i][j]) winCnt += 1;
            if(j !== i && arr[j][i]) loseCnt += 1;
        }
        
        if(loseCnt + winCnt === n-1) answer += 1;
    }
    
    function explore(start, mid, results, arr) {
        for(let result of results) {
            const [a, b] = result;
            if(mid === a) {
                if(arr[start-1][b-1] !== true) explore(start, b, results, arr);
                arr[start-1][b-1] = true;
            }
        }
    }
    return answer;
}

こうやって解いて通過したのですが、recursionになったせいか、結構時間がかかりました.クイック解答を調べてみるとfloydとshallアルゴリズム(すべての頂点から別の頂点への最短経路を求めるアルゴリズム)を使っている人が多いことがわかりました.フロイドとシャーロットで交換した接着剤は以下の通りです.

function solution(n, results) {
    var answer=0;
    const arr = new Array(n).fill(null).map(sub => sub = new Array(n).fill(false));
    
    results.map(result => {
        const [win, lose] = result;
        arr[win-1][lose-1] = true;
    });
    
  	// 플로이드 와샬
    for(let i = 0; i < n ; i += 1){
        for(let a = 0 ; a < n ; a += 1){
            for(let b = 0 ; b < n ; b += 1){
              	// a가 i를 이기고 i가 b를 이기면 a는 b를 이긴다.
                if(arr[a][i] === true && arr[i][b] === true) arr[a][b] = true;
            }
        }
    }

    for(let i = 0; i < n; i += 1) {
        let winCnt = 0;
        let loseCnt = 0;
        for(let j = 0; j < n ; j += 1) {
            if(j !== i && arr[i][j] === true) winCnt += 1;
            if(j !== i && arr[j][i] === true) loseCnt += 1;
        }
        
        if(winCnt + loseCnt === n - 1) answer += 1;
    }
    
    return answer;
}