programmers - 순위

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

코딩테스트 연습 - 순위

• 이 문제는 그래프 문제로 주어진 results 리스트를 활용해서 그래프를 먼저 그리고 시작했다.
• 이긴 사람 집단과 진 사람 집단을 만들어서 먼저 그래프를 구현해줬다.
• 이 문제의 포인트는 b가 a를 이겼을 때, c가 b를 이겼으면 c는 a보다 높은 순위라는 점이다.
• 이 문제 예시에서도 2번이 5번을 이겼고, 2번이 1,3,4한테 졌으면 5번은 당연히 1,3,4보다는 아래 순위를 기록하게된다.
• winner와 loser의 딕셔너리를 만들어주고, for문을 통해서 입력값 results를 통해 그래프를 만들어줬다.
• 그리고 주어진 n만큼의 인원수를 for문을 돌리면서 누가 누구한테 졌고 이겼는지를 판단해서 위에 말했던 포인트를 유념해서 update해주는 방식으로 구현했다.

def solution(n, results):
    answer = 0
    winner = {i:set() for i in range(1,n+1)}
    loser = {i:set() for i in range(1,n+1)}
    for win, lose in results:
        winner[win].add(lose)
        loser[lose].add(win)
    for i in range(1,n+1):
        for lose in winner[i]:
            loser[lose].update(loser[i])
        for win in loser[i]:
            winner[win].update(winner[i])
    for i in range(1,n+1):
        if len(loser[i]) + len(winner[i]) == n-1:
            answer += 1
    return answer