순위

문제설명

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

---

풀이

순위를 확실히 알기 위해선 해당 사람이 이기고 진 정보의 갯수 합이 n-1개가 되어야 한다. 여기서 중요한 점은

• A를 이긴 사람은 A에게 진 사람을 이기고
• A에 진 사람은 A에게 이긴 사람에 진다

는 것이다.

def solution(n, results):
    answer = 0
    # win[i] : i가 이긴 사람의 집합
    # lose[i] : i가 지는 사람의 집합
    win, lose = {}, {}
    for i in range(1, n+1):
        win[i], lose[i] = set(), set()
    for result in results:
        win[result[0]].add(result[1])
        lose[result[1]].add(result[0])
    for i in range(1, n+1):
        for winner in lose[i]:
            win[winner].update(win[i])
        for loser in win[i]:
            lose[loser].update(lose[i])
    
    for i in range(1, n+1):
        if len(win[i]) + len(lose[i]) == n-1:
            answer += 1

        
    return answer