문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
우선 경기 결과 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.2] 피로도 (Python) (0) | 2024.10.01 |
---|---|
[프로그래머스 Lv.3] 길 찾기 게임 (Python) (2) | 2024.09.30 |
[프로그래머스 Lv.3] 가장 먼 노드 (Python) (1) | 2024.09.28 |
[프로그래머스 Lv.2] 기능개발 (Python) (2) | 2024.09.26 |
[프로그래머스 Lv.2] 주식가격 (Python) (5) | 2024.09.21 |