[Python] 순위

1. 문제

 

 

 

2. 풀이 과정

방법 1) 자신의 앞과 뒤에 있는 선수 수의 합이 n-1개면 정확한 순위를 알 수 있다. 한 노드씩 차례대로 살펴보면서, 자신을 이긴 선수와 진 선수의 수를 구한다. 자신을 이긴 선수를 stack에 넣고 꺼내서 그 선수를 이긴 선수들까지 계속 count해나간다.

def ncount(n, g, start):
    visited = [False]*n
    stack = [start]
    visited[start] = True
    
    while stack:
        n = stack.pop()
        
        for i in g[n]:
            if not visited[i]:
                visited[i] = True
                stack.append(i)
                
    return visited.count(True)-1
        

def solution(n, results):
    graph = [[] for _ in range(n)]
    graph_r = [[] for _ in range(n)] #반대방향 그래프
    result = [0]*n
    
    for f, t in results:
        graph[f-1].append(t-1)
        graph_r[t-1].append(f-1)
        
    for i in range(n):
        result[i] += ncount(n, graph, i) #자신의 뒤에 있는 노드 수
        result[i] += ncount(n, graph_r, i) #자신의 앞에 있는 노드 수
        
    return result.count(n-1) #자신의 앞, 뒤에 있는 노드 수의 합이 n-1이면 확실

 

방법 2) 원리는 방법 1)과 같지만 구현 방식에서 이 방법이 약 2배 빠르다.

from collections import defaultdict
def solution(n, results):
    win = defaultdict(set)
    lose = defaultdict(set)
    
    for w, l in results:
        win[w-1].add(l-1)
        lose[l-1].add(w-1)
        
    for i in range(n):
        for winner in lose[i]: #내가 i한테 졌다
            win[winner].update(win[i]) #나를 이긴 선수에게 내가 이긴 선수 더하기
        for loser in win[i]:
            lose[loser].update(lose[i])
            
    answer = 0
    for j in range(n):
        if len(win[j])+len(lose[j]) == n-1: 
            answer += 1
    return answer