[프로그래머스] 순위 - 파이썬(python)

 

 

나의 풀이

from collections import deque

def find_person(winner, loser, node) :
    q = deque()
    visited = [False] * (len(winner)+1)
    
    for i in winner[node] :
        q.append(i)
        
    while q :
        x = q.popleft()
        for i in winner[x] : 
            if not visited[i] : # 아직 탐색하지 않은 선수라면
                visited[i] = True
                winner[node].add(i) # 내가 이길 수 있는 사람에 i를 추가
                loser[i].add(node) # i가 지는 사람에 나를 추가
                q.append(i)

def solution(n, results):
    winner = [set([]) for _ in range(n+1)] # 내가 이길 수 있는 사람을 저장
    loser = [set([]) for _ in range(n+1)] # 나보다 잘하는 사람을 저장
    
    for w, l in results :
        winner[w].add(l)
        loser[l].add(w)
        
    for i in range(1, n+1) :
        find_person(winner,loser, i)
   
    num = 0
    for i in range(1, n+1) :
        if len(set(winner[i])) + len(set(loser[i])) + 1 == n :
            num += 1
    return num

• 내가 순위를 정확하게 알 수 있는 사람은 다음과 같다.
  • (나를 이길 수 있는 사람 수 ) + 자기 자신 + (내가 이길 수 있는 사람 수) == n 을 만족하는 사람이다.
• 이를 위해, 내가 이길 수 있는 사람을 저장하는 winner[] , 나를 이길 수 있는 사람을 저장하는 loser[] 를 두었다.
• 그리고, 경기 결과로 winner, loser 를 초기화 하였다.
  • for w, l in results :
            winner[w].add(l)
            loser[l].add(w)
• 그런 다음, BFS 를 통해 winner 와 loser 를 확장시켰다. 
• 내가 이긴 사람이 이긴 사람은 나도 이길 수 있기 때문에, 부모 노드를 끝까지 찾아가는 것과 같은 맥락이다.
• 따라서 1번 선수 ~ n번 선수까지 BFS 를 실행하며 winner[i] 와 loser[i] 에 정보를 저장하였다.
• 이때 한 번 탐색한 선수에 대해서는 중복으로 탐색하지 않으며,
  • 내가 이길 수 있는 선수에 대해서는 winner[나].append(해당 선수) 를 실행한다.
  • 이는 동시에 해당선수는 나를 못이긴다는 뜻이므로 loser[해당 선수].append(나) 를 실행한다.