[프로그래머스 Lv.3] 순위 (Python)

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

프로그래머스

풀이

우선 경기 결과 results를 토대로 승리한 사람들과 패배한 사람들을 파악하여 그래프를 그린다.

모순이 없고 실력이 뛰어난 선수가 항상 이긴다는 보장이 있으므로 만약 B가 A에게 졌다면, A가 진 모든 사람들에게 B도 모두 지게 된다. 같은 맥락으로 A가 B에게 이겼으므로, A는 B가 이긴 모든 사람들에게 이기게 된다.

위와 같은 과정을 반복하여서 모든 선수들의 승/패 관계를 모두 그래프로 표현하게 되었을 때, 자신이 이긴 사람과 진 사람의 수의 합이 n-1이라면 자신의 순위를 파악할 수 있게 됨으로, 이런 사람들의 수를 카운트하면 정답을 알아낼 수 있다.

(예를 들어 자신을 포함하여 4명이 참여했는데 내가 2명한테 이기고 1명에게 패했다면, 나의 등수는 2등인 것을 알 수 있다.)

def solution(n, results):
    w_graph = [set() for _ in range(n+1)] # i번째 선수가 승리한 선수들의 인덱스
    l_graph = [set() for _ in range(n+1)] # i번째 선수를 패배시킨 선수들의 인덱스
    
    for result in results: # 경기 결과를 순회하며
        winner, loser = result
        w_graph[winner].add(loser) # winner가 loser에게 승리함을 그래프에 표시
        l_graph[loser].add(winner) # loser가 winner에게 패배함을 그래프에 표시
    
    for idx in range(1, n+1): # 그래프를 순회하며
        wins = w_graph[idx] # i번째 사람이 승리한 선수들
        loses = l_graph[idx] # i번째 사람을 패배시킨 선수들
        
        for win in wins: l_graph[win].update(loses) # i번째 선수가 승리한 선수들은 i번째 선수를 패배시킨 사람들에게 무조건 패배
        for lose in loses: w_graph[lose].update(wins) # i번째 사람을 패배시킨 사람들은 i번째 사람이 승리한 사람들에게 무조건 승리
        
    cnt = 0
    for idx in range(1, n+1):
        if len(w_graph[idx]) + len(l_graph[idx]) == n-1: # 자신이 승리한 선수들과 자신을 패배시킨 선수들의 합이 n-1이라면 순위를 결정할 수 있음
            cnt += 1
            
    return cnt