[자바] 프로그래머스 - 순위 [코딩테스트 연습 Lv3]

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

코드 : https://github.com/NaHwaSa/Programmers_OnlineJudge/blob/main/Level%203/%EC%88%9C%EC%9C%84.java

 

 

  방향 그래프로 표현할 수 있는 문제의 경우 일단 그래프로 그려보면 답이 보이는 경우가 많다. 따라서 일단 무지성으로 그려봤다.

 

  그럼 길찾기 처럼 거리를 한번 재보자! 정확힌 어디까지 갈 수 있는지만 알 수 있으면 된다.

arr[i][j]를 대해 i번에서 j번까지의 거리라고 생각하고 표를 작성하면 아래와 같다.

 

  그럼 이쯤에서 이 문제를 풀 수 있는 아이디어를 찾을 수 있다. 저기 '5'의 경우 4명한테 져서 순위가 확정됬음을 알 수 있다. '2'의 경우 자신을 이긴 번호가 3개, 자신이 이긴 번호가 1개이다. 더해보면 4명이다.

즉, [자신이 이긴 번호의 개수 + 자신을 이긴 번호의 개수 = N-1] 이라면 순위를 확정할 수 있는 것이다.

 

--------

  만약 위를 더한게 N이상이라면? 또는 합친게 N-1이긴한데, 이긴 사람의 수와 자길 이긴 사람의 수가 동일한 경우가 있다면(예를들어 2번이 3명을 이기고 1명한테 졌는데, 5번도 3명한테 이기고 1명한테 졌음)? 데이터가 잘못된 경우이다. 하지만 '모든 경기 결과에는 모순이 없습니다.' 조건에 따라 이 부분을 생각하지 않아도 된다.

 

  또한 만약 이 문제에 'A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다'라는 조건이 없었다면 이런식으로 풀 수 없다. 이 경우 자신이 이긴 번호의 개수가 N-1개거나, 자신을 이긴 번호의 개수가 N-1 일때만 순위를 알 수 있다. (해당 조건이 없을 경우 1번이 2번 이겼고 2번이 3번을 이겼다고 해서 1번이 3번을 이길 수 있는게 아니므로)

 

  그리고 방향 그래프의 간선을 위 풀이와 반대로 '진사람->이긴사람'으로 연결했다 해도 상관없다. 풀이에 변경점은 없다. 아무튼 자기가이긴사람수 + 자길이긴사람수 = N-1명 이면 된다. 

--------

 

다시 풀이로 돌아와서, 자신이 이긴 번호의 개수는 어떻게 알 수 있을까?

이렇게 가로로 보고 도달 가능한 위치라면(거리에 관계없이 도달만 할 수 있다면) 카운팅하면 된다. 당연히 갈 수 있는지만 알면 되므로, 거리정보는 무의미하다. 

 

자신을 이긴 번호의 개수는 그럼 아래와 같이 세로로 보면 될 것임을 알 수 있다.

그럼 세보자.

1 : 이긴사람 3명 + 자길이긴사람 0명 = 3명

2 : 1명 + 3명 = 4명

3 : 2명 + 1명 = 3명

4 : 3명 + 0명 = 3명

5 : 0명 + 4명 = 4명

 

N=5 이므로, N-1명에 대한 정보가 있어 '2'와 '5'는 순위를 확정할 수 있다.

 

 

최종적으로 저 표를 구할수만 있다면 이제 문제를 풀 수 있게 됬다. 어떻게 저 표를 만들까?

사실 최대 선수의 수가 100명이므로 뭘 써도 된다. 100명 각각에 대해 BFS 돌려도 되고, 마찬가지로 각각에 대해 다익스트라 돌려도 된다. 내 경우엔 O(N^3)이지만 가장 강력하고(한방에 모든 사람으로부터 모든 사람까지의 거리를 구할 수 있음), 구현이 쉬운(대충 3중 반복문 하나면 끝) 플로이드-와샬 알고리즘으로 구현했다. 내 경우엔 그냥 일반 플로이드-와샬 형태처럼 거리를 구했는데 거리 정보는 무의미하므로 그냥 boolean 배열로 돌려도 된다. 코드 기준으로 arr[i][k] && arr[k][j] 라면 k를 경유해서 i에서 j로 갈 수 있음을 활용하면 된다.