[ 프로그래머스 / LV3 / 파이썬 Python ] 순위

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

프로그래머스

 

코드

---

from collections import defaultdict

def solution(n, results):
    answer = 0
    lose_dict = defaultdict(set) 
    win_dict = defaultdict(set)
    
    for a,b in results:
        win_dict[a].add(b)
        lose_dict[b].add(a)
        
    for i in range(1,n+1):         
        for winner in win_dict[i]:
            lose_dict[winner].update(lose_dict[i])
        for loser in lose_dict[i]:
            win_dict[loser].update(win_dict[i])
    
    for i in range(1,n+1):
        if len(win_dict[i]) + len(lose_dict[i]) == n-1:
            answer += 1

    return answer

 

풀이

---

문제의 조건들을 살펴보자

1. A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이긴다.
2. 경기는 1대1 방식이다.
3. 정확하게 순위를 매길 수 있는 선수들의 수를 구한다.

1번 조건을 통해서 복잡한 관계를 형성될 수 없다는 것을 알 수 있다.

예를 들어, A가 B를 이기고 B는 C를 이겼는데 C가 A를 이기는 싸이클이 생길수는 없다는 것이다.

 

3번 조건을 보고 처음 생각한 것이 "나보다 잘하는 선수의 수" + "나보다 못하는 선수의 수" = "전체 -1"이면 그 선수의 정확한 순위를 알 수 있다는 것이다.

 

구현의 편의성을 위해 defaultdict를 사용했다.

• win_dict[x] : x에게 진 사람들의 목록
• lose_dict[x] : x에게 이긴 사람들의 목록

위의 코드가 조금 이해하기에 복잡할 수 있지만 여기서 구현하는 내용은 다음과 같다.

" 나에게 이긴 사람들은 나에게 진 사람들에게 모두 이기고, 나에게 진 사람들은 나에게 이긴 모두에게 진다"

 

이 코드를 거치면 문제에서 주어준 results의 내용대로 모든 순서를 만들어낼 수 있다.