[프로그래머스] LV.3 순위 / 파이썬(Python)

📜 문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

🔗 문제 링크

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

프로그래머스

 

💡 문제 풀이

입출력 예시

정확하게 순위를 매길 수 있는 선수의 수를 구해야 한다. 정확하게 순위를 매기기 위해서는 해당 선수에 대한 경기 결과가 n - 1개 주어져야 한다. 위의 입출력 예시로 생각해보면 전체 선수가 5명이니까 한 선수가 4명이랑 경기한 결과가 있으면 정확한 순위를 알 수 있다.

어떤 선수가 어떤 선수에게 이기고 졌는지 쉽게 저장해 둘 수 있는 파이썬 defaultdict를 써보기 딱 좋은 문제이다.

이 문제의 풀이 과정은 3단계로 볼 수 있을 것 같다.

1. for문을 돌면서 어떤 선수가 어떤 선수에게 이겼는지를 wins에 어떤 선수가 졌는지를 loses에 담아준다.
          wins 딕셔너리 안의 정보
   
   • 4번 선수가 2, 3번 선수를 이겼다.
   • 3번 선수가 2번 선수를 이겼다.
   • 1번 선수가 2번 선수를 이겼다.
   • 2번 선수가 5번 선수를 이겼다.
     loses 딕셔너리 안의 정보
   • 3번 선수가 4번 선수한테 졌다.
   • 2번 선수가 1, 3, 4번 선수한테 졌다.
   • 5번 선수가 2번 선수한테 졌다.

승패 결과

  2. 두 딕셔너리의 공통된 정보를 이용해서 합집합을 만든다
      그러면 아래처럼 정보가 종합된 합집합 defaultdict가 만들어진다.

defaultdict로 합집합 만든 결과

  3. 합집합을 만든 딕셔너리를 순회하면서 특정 선수에 대한 정보가 승리 정보와 패배 정보를  합쳐서 n - 1개 있으면 정확한 순위를 알 수  있는 선수이다. 이 방식으로 답을 구할 수 있다.

# defaultdict import
from collections import defaultdict

def solution(n, results):
    answer = 0

    # 누가 누굴 이기고 누가 누구한테 졌는지 보여줄 dict
    wins = defaultdict(set)
    loses = defaultdict(set)
	
    for i, j in results:
        wins[i].add(j)
        loses[j].add(i)

    for i in range(1, n + 1):
        # 합집합 구하기
        for loser in wins[i]:
            loses[loser] |= loses[i]

        for winner in loses[i]:
            wins[winner] |= wins[i]
	
    # 확인해봤을 때 승패의 정보가 n - 1개 있으면 명확히 알 수 있는 선수
    for i in range(1, n + 1):
        if len(wins[i]) + len(loses[i]) == n - 1:
            answer += 1

    return answer