문제 링크
풀이 과정
•
본 문제는 코드 주석으로 풀이 과정을 대체합니다.
전체 코드
from collections import defaultdict
def solution(n, results):
'''
1) A 선수에게 진 B 선수는, A 선수로부터 승리한 선수한테도 패배한다.
2) A 선수로부터 승리한 B 선수는, A 선수에게 패배한 선수로부터 승리한다.
'''
answer = 0
win_graph = defaultdict(set) # 각 선수 별 승리를 거둔 선수의 집합 ex) 2: {5}
lose_graph = defaultdict(set) # 각 선수 별 패배를 당한 선수의 집합 ex) 2: {1, 3, 4}
for winner, loser in results:
win_graph[winner].add(loser)
lose_graph[loser].add(winner)
for i in range(1, n+1):
# case 1) A 선수에게 진 B 선수는, A 선수로부터 승리한 선수한테도 패배한다.
for loser in win_graph[i]:
lose_graph[loser].update(lose_graph[i])
# case 2) A 선수로부터 승리한 B 선수는, A 선수에게 패배한 선수로부터 승리한다.
for winner in lose_graph[i]:
win_graph[winner].update(win_graph[i])
# 이긴 선수 합과 진 선수의 합이 n-1(자기 자신은 제외하므로)이면, 순위가 고정됩니다.
for i in range(1, n+1):
if len(win_graph[i]) + len(lose_graph[i]) == n-1:
answer += 1
return answer
Python
복사