프로그래머스 - 순위 (feat. Python)

[순위]

프로그래머스

 

문제 접근

• 플로이드 워샬 알고리즘
  • A와 B, B와 C의 관계를 알고, A와 C의 관계를 알고 싶을 때 사용
• 승리 결과와 패배 결과를 리스트로 보관한다.
• 결과를 알 수 있는 두 선수(A, B)와 결과를 알고 싶은 두 선수(A, C)를 비교하여 A와 C의 결과를 도출한다
  • A > B // B > C일 때 ⇒ A > C가 된다.
  • 만약, A > B, B > C, C > A인 경우가 있다면??
    • 해당 의문에 대해서는 문제 제한사항에 경기 결과에 모순이 없다는 것을 확인
• 순위 판단
  • 선수 목록을 순회 하면서 A가 B를 이길 수 있는지 모르는 관계는 순위를 정할 수 없다고 판단한다.

 

Code

def solution(n, results):
    answer = 0
    
    winner_list = [[0] * n for _ in range(n)] 
    looser_list = [[0] * n for _ in range(n)]
    
    # 선수의 이기고 진 결기 결과를 담는다
    for player in results:
        winner = player[0]
        looser = player[1]
        
        winner_list[winner-1][looser-1] = 1
        looser_list[looser-1][winner-1] = 1
    
    # A > B, B > C일 때, A <-> C의 결과를 알고싶다면 A는 C가 이긴 선수를 구하면 된다.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if winner_list[i][k] == 1 and winner_list[k][j]:
                    winner_list[i][j] = 1
                    looser_list[j][i] = 1
        
    # 순위를 추정하기
    for i in range(n):
        isTrue = True
        
        for j in range(n):
            if i == j:
                continue
            
            # 이기거나 진 결과를 추정 가능하다면
            if winner_list[i][j] != 1 and looser_list[i][j] != 1:
                isTrue = False
                break
            
        # 경기 결과를 모두 추정 가능하다면
        if isTrue:
            answer += 1
    return answer

 

채점 결과