[프로그래머스 / Python] 순위

문제 링크: programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

 

문제 설명

4번 선수가 2번 선수에게 이기고 2번 선수가 5번 선수에게 이긴다면, 4번 선수는 결국 5번 선수에게도 이깁니다. 

4번 > 2번, 2번 > 5번 → 4번 > 5번

이런 식으로 모든 선수의 경기 결과를 종합해서 결과의 개수가 (n - 1)개라면 순위를 확정 지을 수 있습니다. 

 

1. 경기 결과를 저장할 win, lose 딕셔너리 초기화
2. results에 있는 경기 결과를 입력 (선수가 겹치지 않게 set 자료형 이용)
3. n명의 선수들의 경기 결과 합치기
   1) 만약 A가 B를 이겼다면 A는 B가 이긴 모든 선수들에게 승리
   2) 만약 A가 B에게 졌다면 A는 B가 진 모든 선수들에게 패배
4. 경기 결과의 개수가 (n - 1)개일 경우 순위를 정할 수 있음

 

 

 

소스코드

from collections import defaultdict

def solution(n, results):
    answer = 0
    win, lose = defaultdict(set), defaultdict(set)
    # 경기 결과 입력 받기
    for (winner, loser) in results:
        win[winner].add(loser)
        lose[loser].add(winner)
    # 경기 결과 합치기
    for i in range(1, n + 1):
        for winner in lose[i]: win[winner].update(win[i])
        for loser in win[i]: lose[loser].update(lose[i])
    # 경기 결과가 (n - 1)개면 순위를 정할 수 있음
    for i in range(1, n + 1):
        if (len(win[i]) + len(lose[i])) == (n - 1): answer += 1

    return answer