너무 잘짰길래 가져옴
from collections import defaultdict
def solution(n, results):
answer = 0
win, lose = defaultdict(set), defaultdict(set)
for winner, loser in results:
lose[loser].add(winner)
win[winner].add(loser)
for i in range(1, n + 1):
for winner in lose[i]: win[winner] |= win[i]
for loser in win[i]: lose[loser] |= lose[i]
for i in range(1, n+1):
if len(win[i]) + len(lose[i]) == n - 1: answer += 1
return answer
선수의 순위?
본인보다 랭크 낮은사람의 수 + 본인 + 본인보다 랭크 높은사람의 수 == n
이 조건을 만족하는 선수들의 수를 세주면 된다. 그런데 문제는 자기보다 낮거나 높은 사람들의 수를 구해야하는데
나보다 랭크 낮은 사람 수 = 나한테 진사람 수 + 나한테 진사람한테 진사람들
- 나를 이긴 선수한테 나한테 진 선수들을 다 추가 해주자
나보다 랭크 높은 사람 수 = 나한테 이긴사람 수 + 나한테 이긴사람한테 이긴사람들
- 나한테 진 선수한테 나한테 이신 선수들을 다 추가 해주자
내가 가진 정보를, 남들한테 나누어 주자! 이게 핵심입니다.
win, lose
win 사전과, lose 사전의 구성이 헷갈릴 수 있습니다.
win[i]:i한테 진 놈들의 리스트
lose[i]:i한테 이긴 놈들의 리스트
from collections import defaultdict
def solution(n, results):
answer = 0
win, lose = defaultdict(set), defaultdict(set)
for winner, loser in results:
lose[loser].add(winner)
win[winner].add(loser)
for i in range(1, n + 1):
for winner in lose[i]: win[winner] |= win[i] # i 선수를 이긴 선수들에게, i 선수한테 진 선수들을 추가
for loser in win[i]: lose[loser] |= lose[i] # i 선수한테 진 선수들이게, i 선수를 이긴 선수들을 추가
for i in range(1, n+1):
if len(win[i]) + 1 + len(lose[i]) == n: answer += 1 # 진놈들 + 본인 + 이긴놈들 == n ?
return answer