[Python] 프로그래머스(Lv3) - 순위

안녕하세요 :)

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

프로그래머스 그래프 세트에 속해있는 순위 문제입니다.

풀이

문제 예시로 순위를 유추해보면 이렇습니다.
4 1
3 1
2
5
여기서, 2는 상위노드가 (1, 3, 4) 하위노드가(5) 로 상위노드 개수와 하위노드가 개수를 더하면 4개입니다. 즉, (상위노드 개수) + (하위노드 개수) = n-1 이면 정확하게 순위를 매길 수 있습니다.
5를 예시로 해도 이와 같습니다. 5는 상위노드가 (1, 2, 3, 4)로 4개가 있고 하위노드는 없습니다. 총 4개 n-1이므로 5도 순위를 매길 수 있습니다.

1부터 n까지 for문을 돌면서 합집합연산을 통해 이긴사람을 key값으로 갖는 winners와 진사람을 key값으로 갖는 딕셔너리 losers를 구해줍니다.

def solution(n, results):
    winners = {}
    losers = {}

    for i in range(1, n+1):
        winners[i], losers[i] = set(), set()

    for res in results:
        winner, loser = res
        winners[winner].add(loser)
        losers[loser].add(winner)

    for i in range(1, n+1):
        for winner in losers[i]:
            winners[winner] |= winners[i]
        for loser in winners[i]:
            losers[loser] |= losers[i]

    # (부모노드 개수)+(자식노드 개수)== n-1 인 경우 count++
    count = 0
    for i in range(1, n+1):
        if len(winners[i]) + len(losers[i]) == n-1:
            count += 1

    return count