Level 3 순위 Python 3

https://programmers.co.kr/learn/courses/30/lessons/49191?language=python3 

코딩테스트 연습 - 순위

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_순위.py

hwayeon351/Programmers-Algorithms

from collections import defaultdict
def solution(n, results):
    answer = 0
    #key = 사람, value = key를 이긴 사람
    winner = defaultdict(set)
    #key = 사람, value = key한테 진 사람
    loser = defaultdict(set)
    for win, lose in results:
        winner[lose].add(win)
        loser[win].add(lose)
    for i in range(1, n+1):
        #i를 이긴 사람들은 i한테 진 사람들도 이긴다
        for w in winner[i]:
            loser[w].update(loser[i])
        #i한테 진 사람들은 i를 이긴 사람들한테도 진다
        for l in loser[i]:
            winner[l].update(winner[i])
    for i in range(1, n+1):
        if len(winner[i]) + len(loser[i]) == n-1: answer += 1
    return answer

---

풀이 과정

풀이 시간 1시간 10분

key를 이긴 사람들을 value로 하는 winner 딕셔너리와 key한테 진 사람들을 value로 하는 loser 딕셔너리를 만들어서 주어진 results를 통해 딕셔너리를 최대한 채운다. 그 다음 key값을 기준으로winner와 loser의 value의 개수가 n-1이라면 key의 순위를 알 수 있다.

from collections import defaultdict
def solution(n, results):
    answer = 0
    #key = 사람, value = key를 이긴 사람
    winner = defaultdict(set)
    #key = 사람, value = key한테 진 사람
    loser = defaultdict(set)
    for win, lose in results:
        #lose를 이긴 사람에 win을 추가
        winner[lose].add(win)
        #win에게 진 사람에 lose를 추가
        loser[win].add(lose)
        
    for i in range(1, n+1):
        #i를 이긴 사람들은 i한테 진 사람들도 이긴다
        for w in winner[i]:
            loser[w].update(loser[i])
        #i한테 진 사람들은 i를 이긴 사람들한테도 진다
        for l in loser[i]:
            winner[l].update(winner[i])

    for i in range(1, n+1):
        #i를 이긴 사람의 수와 i한테 진 사람의 수가 n-1인 경우, i의 순위를 알 수 있으므로 +1
        if len(winner[i]) + len(loser[i]) == n-1: answer += 1
    return answer
#시간복잡도 = O(n^3) 공간복잡도 = O(n^2)