[프로그래머스] 순위 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

고민고민하다가 접근법을 모르겠어서 검색해본 문제이다.

접근방법은 플로이드와샬로 하면 됐었다.

 

a가 b를 이겼다면 b는 항상 a 아래이고, b가 c를 이겼다면 c도 항상 b 아래이다

결국 c는 항상 a아래 이므로

a->b, b->c이면 a->c 인 것이므로 플로이드와샬로 접근이 가능하다.

 

a와 b 관계에서 a가 c를 이기고 c가 b를 이기는 관계가 있으면

a가 b를 이긴것으로 체크하고 (b,a), (c,a), (b,c)는 모두 진것으로 체크하면 된다.

마지막으로 순위가 결정되려면 모든 선수와 다 겨뤄봐야하므로 체크된 값의 개수가 n-1이거나 체크되지 않은 값이 1이면 된다.

 

def solution(n, results):
    answer = 0
    board = [[0]*n for _ in range(n)]
    
    for a,b in results:
        board[a-1][b-1] = 1
        board[b-1][a-1] = -1
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j or board[i][j] in [1,-1]:
                    continue
                if board[i][k] == board[k][j] == 1:
                    board[i][j] = 1
                    board[j][i] = board[k][i] = board[j][k] = -1
    for row in board:
        if row.count(0) == 1:
            answer += 1
    return answer