https://school.programmers.co.kr/learn/courses/30/lessons/49191
문제 정의
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return
results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미이다.
접근 방법
- 순위가 정해지는 의미가 어떤 것인지 잘 파악해야 한다. 👉 순위가 정해진다 == 나 제외 모든 선수와 경기를 해서 승패가 갈렸다.
- 또한 i가 k를 이기고, k가 j를 이기면 i가 j를 이긴다는 연쇄적인 특징을 반영해 그래프를 업데이트 해야한다.
- 플로이드 와샬 알고리즘을 활용해 풀 수 있다.
문제 해설
[딕셔너리 사용할 경우]
- 그래프를 만들고 승패에 따라 승자와 패배자에 대한 정보를 업데이트 해준다.
- 자기 자신을 제외한 나머지 노드와 겨뤄서 승패가 결정된 노드가 순위가 정해진 노드이다.
[플로이드 와샬 사용할 경우]
- 인접행렬로 그래프의 정보를 나타내준다.
- 연결이 없는 관계는 None, i가 j를 이기면 True, 지면 False로 업데이트 해준다.
- 징검다리 처럼 건너건너 이기거나 졌다면 해당되는 노드의 승패 여부도 업데이트 해준다.
풀이
- 딕셔너리 사용
from collections import defaultdict
def solution(n, results):
answer = 0
win_graph = defaultdict(set) # 이긴 애들
lose_graph = defaultdict(set) # 진 애들
for winner,loser in results: # 결과에서 이기고 진 애들 그래프화
win_graph[loser].add(winner)
lose_graph[winner].add(loser)
# defaultdict(<class 'set'>, {3: {4}, 2: {1, 3, 4}, 5: {2}})
# defaultdict(<class 'set'>, {4: {2, 3}, 3: {2}, 1: {2}, 2: {5}})
for i in range(1,n+1):
for winner in win_graph[i]: # i한테 진 애들은 i를 이긴 애들한테도 진 것
lose_graph[winner].update(lose_graph[i])
for loser in lose_graph[i]: # i한테 이긴 애들은 i한테 진 애들한테도 이긴 것
win_graph[loser].update(win_graph[i])
# defaultdict(<class 'set'>, {3: {4}, 2: {1, 3, 4}, 5: {1, 2, 3, 4}, 1: set(), 4: set()})
# defaultdict(<class 'set'>, {4: {2, 3, 5}, 3: {2, 5}, 1: {2, 5}, 2: {5}, 5: set()})
for i in range(1,n+1):
if len(win_graph[i]) + len(lose_graph[i]) == n-1: # i한테 이기고 진 애들 합쳐서 n-1이면 순위가 결정된 것(모든 경기를 다 한것이니까)
answer += 1
return answer
- 플로이드 와샬 사용
def solution(n, results):
answer = 0
# 그래프 정보 입력
graph = [[None for _ in range(n+1)] for _ in range(n+1)]
for win, los in results:
graph[win][los] = True # i가 j를 이기면, True
graph[los][win] = False # 반대의 경우를 False로 설정
# 플로이드와샬 구현하기
for i in range(1, n+1):
for j in range(1, n+1):
for k in range(1, n+1):
if graph[j][i] == None:
continue
if graph[j][i] == graph[i][k]:
graph[j][k] = graph[j][i]
graph[k][j] = not graph[j][i]
# 정확하게 순위를 매길 수 있는 선수 찾기
for i in range(1, n+1):
if None in graph[i][1:i] + graph[i][i+1:]:
continue
answer += 1
return answer
정리
- 플로이드와샬의 시간복잡도는 이다.
- 하지만 이 문제에서
경기 결과는 1개 이상 4,500개 이하,선수의 수는 100 이하라고 되어있으니 완전 탐색으로 풀어도 시간 초과를 걱정하지 않아도 된다.
- 맨 처음 그래프 중 ‘트리’로 접근해서 부모와 자식 노드의 개수에 따라 순위를 고려하려고 했으나 쉽게 아이디어가 떠오르지 않았다.
- 이 문제는 ‘순위’를 정확히 알 수 있다는 점이 무슨 의미인지 아는 것이 중요한 포인트인 것 같다.
참조
[프로그래머스] 순위 #파이썬 #그래프 #Floyd-Warshall #Level3
https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 re..
Uploaded by N2T
