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

문제 출처 : programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

문제 풀이 : 

• 그래프 로 분류 되어있는 문제인데 그래프 라기보단 논리 문제라고 생각했다.
• 처음 문제를 보았을때 손으로 쓰면 간단하게 파악하는 로직(A가 B에게 지고 B가 C에게 진다면 A는 C에게 진다) 를 어떻게 코딩해야하는지 의문이였다.
• 그 다음으로 의문점은 지고 이기는 관계를 파악했을 때 해당 선수의 순위를 결정할 수 있는 기준을 어떻게 처리해야하는지가 의문이였다.
• 다른 블로그를 참고하여(inspirit941.tistory.com/entry/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%9C%EC%9C%84-Level-3) 알게 되었지만 순위를 결정하기 위해선 해당선수의 지고, 이긴 선수 갯수가 n-1개이면 결정할 수 있다는 것을 알 수 있었다.

def solution(n, results):
    answer = 0
    win = {}
    lose = {}
    for i in range(1,n+1):
        win[i]=set()
        lose[i]=set()

    for i in results:
        winner ,loser = i[0],i[1]
        win[winner].add(loser)
        lose[loser].add(winner)

    for i in range(1,n+1):
        #lose[i] : i가 진 사람들
        #win[i] : i가 이긴사람들
        #i가 진 사람들은 모두 i가 이긴 사람들을 이긴다.
        for winner in lose[i]:
            win[winner].update(win[i])
        #i에게 진사람들은 i를 이긴사람들에게 모두 진다.
        for loser in win[i]:
            lose[loser].update(lose[i])

    for i in range(1,n+1):
        if(len(lose[i])+len(win[i])==n-1):
            answer+=1

    return answer