문제
접근
얼핏보고 위상 정렬인줄 알았다.
위상 정렬로 풀려고 하다보니 쉽게 풀리지 않아서, 처음부터 다시 생각해보게된 문제.
핵심은 A가 B를 이겼고, B가 C를 이겼다면 A도 C를 이긴셈이다.
이 연결관계를 표현할 수 있어야한다.
모든 연결 관계를 포함했을 때 A에게 진사람과 이긴 사람의 수가 n-1이면 순위를 표현할 수 있다.
즉, 그래프로 따지면 이동거리가 2이상인 경우도 셀 수 있어야 한다.
문제에서 주어진 결과로 딕셔너리 내에 집합을 만들어준다.
그리고 해당 집합에 건너건너인 경우들을 추가해준다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(n, results):
wins = {}
loses = {}
for i in range(1, n+1):
wins[i] = set()
loses[i] = set()
for winner, loser in results:
wins[winner].add(loser)
loses[loser].add(winner)
for i in range(1,n+1):
for winner in loses[i]:
wins[winner].update(wins[i])
for loser in wins[i]:
loses[loser].update(loses[i])
answer = 0
for i in range(1,n+1):
if len(wins[i]) + len(loses[i]) == n-1:
answer+=1
return answer