프로그래머스. 순위

https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

먼저 한 사람의 순위를 확정하기 위해서는 해당하는 사람의 확실한 승패를 알고있는 경기가 n-1개여야 한다. (n은 총 사람수)

입력이 results 배열이 다음과 같이 주어지면 

 

results = {{4,3}, {4,2}, {3,2}, {1,2}, {2,5}}

 

4 wins 3

4 wins 2

3 wins 2

1 wins 2

2 wins 5

 

라는 것인데 

3번 사람을 보면, 3번은 2번을 이겼다 and 2번은 5번을 이겼다.

따라서 3번은 5번을 이겼다고 할수 있다.

이 문제의 핵심은 이렇게 직접적으로 나와있지 않은 승패를 모두 찾는 것이다. 

 

찾는 방법은 그냥 3단 for loop를 돌리면 되지만 그 방식은 Floyd Warshall 과 유사하다고 볼 수 있다.

a가 b를 이겼다면 

b가 c를 이겼는지 확인하고 이겼다면

a가 c를 이겼다고 볼 수 있다.

 

이렇게 직접적으로 나와있지 않은 승패를 모두 구하고

한 사람을 기준으로 그 사람이 이겼거나 진 경기가 n-1개 있는지 확인하면 된다.

       승                     패

(1 wins 2) or (2 wins 1) 

(1 wins 3) or (3 wins 1) 

...

 

이겼거나 진 경기가 있다면 카운트를 늘려주고 카운트가 n-1개 라면 해당 선수의 등수를 확정지을수 있다.