🥇[プログラマー]ランキング


問題の説明


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

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

    私の答え

    function solution(n, results) {
        const arrayN = Array.from(Array(n),(_,i) => i+1)
        const winHistory = {}
        const loseHistory = {}
        // 대진표 각 번호 별 상황을 등록
        arrayN.forEach(item => {
            winHistory[item] = new Set([])
            loseHistory[item] = new Set([])
        })
        
        results.forEach(result => {
            const [winner, loser] = result
            winHistory[winner].add(loser)
            loseHistory[loser].add(winner)
        })
        
        arrayN.forEach((n) => {
            // i 선수를 이긴 선수 수 만큼 반복
            for(const winI of loseHistory[n]) {
                // 승리 명단에 없다면 추가 X
                if(!winHistory[winI]) continue
                // i 에게 진 선수를 i를 이긴 선수에게 복사
                for(const loser of winHistory[n]) {
                    winHistory[winI].add(loser)
                }
            }
            
            // i 에게 진 선수 수 만큼 반복
            for(const loser of winHistory[n]) {
                // 패배 명단에 없다면 추가 X
                if(!loseHistory[loser]) continue
                // i 에게 진 선수는 i를 이긴 선수에게도 패배
                for(const winner of loseHistory[n]) {
                    loseHistory[loser].add(winner)
                }
            }
        })
        
        return arrayN.reduce((prev,next) => (winHistory[next].size + loseHistory[next].size === n-1 ? prev+1 : prev ) ,0)
    }

  • 勝利リストと失敗リストの幹線をつなぐ

  • 1番選手から、失敗した選手に負かされた選手、勝利した選手に全部負かされました!重要だ!

  • 勝利の試合数+自分==n-1で順位が決まるので、答えは+1