[programmers] 순위

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 예 설명

• 2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
• 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

Idea

직관적으로 이해가 쉽게 되었는지, 레벨3단계치고는 쉽게 풀었습니다.
아마 이 문제를 어렵게 낸다면 낼 수도 있을것 같네요.
“전체 선수들 순위를 나타내어라” 라던지..

Code

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

Explain

예를 들어서 1번이 2번한테서 이겼고,
2번은 3번한테서 이겼다고 한다면,
1번은 3번한테서도 이겼다라는 가정으로 문제를 풀 수 있다.

UFC로 비유를 하자면 랭킹 40등 선수가 랭킹 2등 선수를 이기게 되면 타이틀전을 할 수 있듯이
그렇게 진 경우도 구한다음에,
이제 자기 자신을 제외한 모든 선수들과 경기를 치루게 된것같은 기록이 생긴다면(꼭 다 경기를 치를 필요는 없다. 위에서 처럼, 내가 이긴선수가 이긴선수도 이긴거니까) 본인의 등수를 알 수 있게된다.

처음에는 list로만 풀려고 접근했는데, 딕셔너리와 셋이 더 좋을것같아서 변경했습니다.

다른 풀이 #1

코드가 비슷비슷합니다.

from collections import defaultdict
def solution(n, results):
    answer = 0
    win, lose = defaultdict(set), defaultdict(set)
    for result in results:
            lose[result[1]].add(result[0])
            win[result[0]].add(result[1])

    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

다른 풀이 #2