[Level3] 순위

🛠 문제

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

👩🏻‍💻 해결 방법

문제 풀이를 참고해도 이해하기 어려웠던 문제였다...
우선 win, lose에는 각각 내가 이긴 선수, 나를 이긴 선수의 번호를 저장해주었다
따라서 win[i]안의 번호들은 loser가 되는 것이고, 이들은 lose[i]에 있는 번호들에게도 질 것이므로 lose[loser].update(lose[i])를 해주었다
반대로 lose[i]안의 번호들은 winner가 되는 것이고, 이들은 win[i]에 있는 번호들도 이길 것이므로 win[winner].update(win[i])를 해주었다
이후에 win과 lose의 길이 합이 n-1(자신 제외)이면 answer+1을 해주었다
다시 생각해도 이해하기 어려운 문제다...

소스 코드

def solution(n, results):
    win, lose = {}, {}
    for i in range(1, n + 1):
        win[i], lose[i] = set(), set()
    
    for i in range(1, n + 1):
        for r in results:
            if r[0] == i:
                win[i].add(r[1])
            if r[1] == i:
                lose[i].add(r[0])
        
        for winner in lose[i]:
            win[winner].update(win[i])
        for loser in win[i]:
            lose[loser].update(lose[i])
            
    answer = 0
    for i in range(1, n + 1):
        if len(win[i]) + len(lose[i]) == n - 1:
            answer += 1
    return answer

💡 다른 사람의 풀이

def solution(n, results):
    answer = 0
    graph = [[0 for cols in range(n)] for rows in range(n)]
    for r in results:   #그래프 초기화
        graph[r[0]-1][r[1]-1] = 1
        graph[r[1]-1][r[0]-1] = -1
    for i in range(n):  #각 행별로 처리
        for j in range(n):
            if graph[i][j] == 1:
                for m in range(n):
                    if graph[j][m] == 1 and graph[i][m] == 0:
                        graph[i][m] = 1
                        graph[m][i] = -1
            elif graph[i][j] == -1:
                for m in range(n):
                    if graph[j][m] == -1 and graph[i][m] == 0:
                        graph[i][m] = -1
                        graph[m][i] = 1
    for i in range(n):
        if graph[i].count(0) == 1:
            answer += 1
    return answer