22034-ランキング


◾ランキング:プログラマーLEVEL 3

  • 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

    のり付け


    1.解説

  • 選手と試合結果の数が少ないので、全体的な探索を行い、結果を探します.
  • まず、試合の結果によって勝、敗を加点する.
  • の増加した試合の結果によって、他の選手の結果が増加した.
  • a選手の勝利結果:b,a選手の失敗結果:c
  • bに属する選手はcに属する選手に敗れます.
  • cに属する選手はbに属する選手に勝つ.
  • set()資料型により,各結果に重複のない追加を行った.合計
  • 2.プログラム


    質問です。


    ◾ランキング:プログラマーLEVEL 3

  • 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

    のり付け


    1.解説

  • 選手と試合結果の数が少ないので、全体的な探索を行い、結果を探します.
  • まず、試合の結果によって勝、敗を加点する.
  • の増加した試合の結果によって、他の選手の結果が増加した.
  • a選手の勝利結果:b,a選手の失敗結果:c
  • bに属する選手はcに属する選手に敗れます.
  • cに属する選手はbに属する選手に勝つ.
  • set()資料型により,各結果に重複のない追加を行った.合計
  • 2.プログラム

  • フロイドとシエル?( https://westmino.tistory.com/20 )
  • コード#コード#


    def solution(n, results):
    answer = 0
    arr = [[0] * (n+1) for i in range(n+1)]
    for a, b in results:
        arr[a][b] = 1
        arr[b][a] = -1
    
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if i == j or arr[i][j] in [1,-1]:
                    continue
                if arr[i][k] == arr[k][j] == 1:
                    arr[i][j] = 1
                    arr[j][i] = arr[k][i] = arr[j][k] = -1
    
    for row in arr:
        if row.count(0) == 2:
            answer += 1
    
    return answer
  • wins,失敗初期化
  • 試合増加
  • 優勝選手優勝
  • 負けた選手は
  • 負けた
  • 各選手の勝利・敗北結果により他選手の結果を推測する.
  • aで勝った選手はaで敗れた選手に敗れた.
  • a敗戦の選手はa優勝の選手に勝つ.
  • の各選手の順位をチェックします.
  • winsで、損失した要素数の和がn-1の場合、順序を指定できます.
  • # 코드
    def solution(n, results):
        answer = 0
        wins = {i : set() for i in range(1, n+1)}
        loses = {i : set() for i in range(1, n+1)}
    
        for a, b in results:
            wins[a].add(b)
            loses[b].add(a)
    
        for i in range(1, n+1):
            for loser in wins[i]:
                loses[loser] = loses[loser].union(loses[i])
            for winner in loses[i]:
                wins[winner] = wins[winner].union(wins[i])
    
        for i in range(1, n+1):
            if (len(wins[i]) + len(loses[i])) == (n-1):
                answer += 1
    
        return answer