문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191
풀이
우선 경기 결과 results를 토대로 승리한 사람들과 패배한 사람들을 파악하여 그래프를 그린다.
모순이 없고 실력이 뛰어난 선수가 항상 이긴다는 보장이 있으므로 만약 B가 A에게 졌다면, A가 진 모든 사람들에게 B도 모두 지게 된다. 같은 맥락으로 A가 B에게 이겼으므로, A는 B가 이긴 모든 사람들에게 이기게 된다.
위와 같은 과정을 반복하여서 모든 선수들의 승/패 관계를 모두 그래프로 표현하게 되었을 때, 자신이 이긴 사람과 진 사람의 수의 합이 n-1이라면 자신의 순위를 파악할 수 있게 됨으로, 이런 사람들의 수를 카운트하면 정답을 알아낼 수 있다.
(예를 들어 자신을 포함하여 4명이 참여했는데 내가 2명한테 이기고 1명에게 패했다면, 나의 등수는 2등인 것을 알 수 있다.)
def solution(n, results):
w_graph = [set() for _ in range(n+1)] # i번째 선수가 승리한 선수들의 인덱스
l_graph = [set() for _ in range(n+1)] # i번째 선수를 패배시킨 선수들의 인덱스
for result in results: # 경기 결과를 순회하며
winner, loser = result
w_graph[winner].add(loser) # winner가 loser에게 승리함을 그래프에 표시
l_graph[loser].add(winner) # loser가 winner에게 패배함을 그래프에 표시
for idx in range(1, n+1): # 그래프를 순회하며
wins = w_graph[idx] # i번째 사람이 승리한 선수들
loses = l_graph[idx] # i번째 사람을 패배시킨 선수들
for win in wins: l_graph[win].update(loses) # i번째 선수가 승리한 선수들은 i번째 선수를 패배시킨 사람들에게 무조건 패배
for lose in loses: w_graph[lose].update(wins) # i번째 사람을 패배시킨 사람들은 i번째 사람이 승리한 사람들에게 무조건 승리
cnt = 0
for idx in range(1, n+1):
if len(w_graph[idx]) + len(l_graph[idx]) == n-1: # 자신이 승리한 선수들과 자신을 패배시킨 선수들의 합이 n-1이라면 순위를 결정할 수 있음
cnt += 1
return cnt
'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스 Lv.3] 가장 먼 노드 (Python) (1) | 2024.09.28 |
---|---|
[프로그래머스 Lv.2] 기능개발 (Python) (2) | 2024.09.26 |
[프로그래머스 Lv.2] 주식가격 (Python) (5) | 2024.09.21 |
[프로그래머스 Lv.4] 도둑질 (Python) (0) | 2024.08.30 |
[프로그래머스 Lv.3] 등굣길 (Python) (0) | 2024.07.27 |