[프로그래머스] 파이썬 _ 순위

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

코딩테스트 연습 - 순위

문제유형 : 그래프,,라는데 나는 좀 다르게 풀었다.

 

 

문제풀이 : 

• 나를 이긴사람을 부모노드로 나에게 진 사람을 자식노드로 구분하여 저장
• 나의 부모노드의수 + 자식노드의 수 = n-1이면 나의 위치는 정해진것이 되므로 answer를 1 증가시킨다.
  • 이때 나의 앞에 있는 애들 ( 즉 나를 이긴애들) 의 자식에게 내 자식을 추가한다.
  • 나의 뒤에있는 애들 ( 즉 나에게 진 애들) 의 부모에게 나의 부모를 추가한다.

 

 

정답코드 : 

def solution(n, results):
    answer = 0
    p = [set() for _ in range(n+1)]
    c = [set() for _ in range(n+1)]
    
    for r in results:
        p[r[1]].add(r[0])
        c[r[0]].add(r[1])   
    
    for i in range(1,n+1):
        for node in p[i]: # i를 이긴 애들 - node
            c[node].update(c[i]) # 나의 앞에있는 애들의 자식에게 나의자식을 준다. 
        for node in c[i]: # i에게 진 애들 - node
            p[node].update(p[i]) # 나의 뒤에있는 애들의 부모에게 나의부모를 준다.
            
    for i in range(1, n+1):
        if len(p[i])+len(c[i]) == n-1:
            answer += 1

    return answer