[프로그래머스] 49191 순위

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

권투 선수 경기결과를 보고 순위를 파악할 수 있는 사람은 순위 파악해보는 문제이다.

코드

from collections import defaultdict

def solution(n, results):
    answer = 0
    winLog = [[0] * (n+1) for _ in range(n+1)]
    
    for w, l in results:
        winLog[w][l] = 1
    
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if winLog[i][j] == 0 and winLog[i][k] and winLog[k][j]:
                    winLog[i][j] = 1
    
    
    for i in range(1, n+1):
        wins = sum(winLog[i])
        loses = 0
        for j in range(1, n+1):
            loses += winLog[j][i]
        if wins + loses == n-1:
            answer+=1
    return answer

승리 기록에 대해서 행과 열번호를 선수 id로 하는 2차원 배열을 만들어서 승리했을 경우에 1이 들어가도록 했다.

그리고 각 선수별로 i선수가 k 선수한테 이기고, k선수가 j 선수한테 이겼는데 i선수와 j선수가 경기한 기록이 없다면 i가 j를 이긴 것으로 판단토록 하는 과정을 거쳤다.

마지막으로 각 선수들이 승리한 횟수와 패배한 횟수를 구해서 그 합이 전체 선수의 수 - 1이 된다면 이 선수는 정확하게 순위를 매길 수 있는 선수이기에 정답에 더해주었다.