[프로그래머스] 순위 - JAVA

프로그래머스

출처 - 프로그래머스

---

알고리즘 

• n명의 선수가 있을 때, 각 선수는 n-1명의 선수와의 승패 여부를 모두 알아야 정확한 순위를 매길 수 있다. 
• 주어진 경기 결과를 이용해서, 다른 선수들 간의 승패 여부를 따지기 위해 플로이드 와샬 알고리즘으로 접근한다. 
• 예를 들어, 1번이 3번을 이기고, 3번이 5번을 이겼다면 → 1번은 5번을 이긴다.

---

 

구현 과정

• player[][] : 각 선수들 간의 승패 여부를 저장할 2차원 배열 (player[i][j] = 1 : i가 j를 이김 / player[i][j] = -1 : i 가 j한테 짐) 

 

1. 주어진 result 배열을 사용해서 i 가 j 한테 이겼을 경우 player[i][j] = 1 로 채운다. 

i가 j한테 이겼다 = j가 i 한테 졌다 
player[i][j] = 1 
player[j][i] = -1

 

2. 플로이드 와샬 알고리즘을 사용해서 나머지 0 부분을 채운다. 

- a가 b를 이기고, b가 c를 이기면 a는 c를 이긴다. if(player[a][b] == 1 && player[b][c] ==1 ) player[a][c] ==1 

- a가 b에게 지고, b가 c에게 지면 a는 c에게 진다. if(player[a][b] == -1 && player[b][c] == -1 ) player[a][c] == -1 

 

 

3. 각 1~n 번까지 각 i번째 선수들 중, player[i] 배열에 0이 아닌 값(1또는-1)이 n-1개 있으면, 순위를 알 수 있는 선수이다.

 

---

 

소스코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int[][] player = new int[n][n];
        
        for(int i=0; i<results.length; i++){
            int win = results[i][0]-1;
            int lose= results[i][1]-1;
            
            //이겼을 경우 : 1, 반대는 졌으니까 : -1
            player[win][lose] = 1; 
            player[lose][win] = -1; 
        }
        
        for(int a=0; a<n; a++){ //경유지 
            for(int b=0; b<n; b++){ //출발지
                for(int c=0; c<n; c++){ //도착지
                    if(player[b][a]== 1 && player[a][c]==1) player[b][c] =1; 
                    if(player[b][a]==-1 && player[a][c]==-1) player[b][c]=-1;
                }
            }
        }//플로이드 와샬
        
        int result=0; 
        //이중에 순위를 확실히 알려면, 채워진 값이 자기자신을 제외한 n-1개 여야함 
        for(int i=0; i<n; i++){
            int cnt=0; 
            for(int j=0; j<n; j++){
                if(player[i][j] !=0 ) cnt++; 
            }
            //순위를 알 수 있음 
            if(cnt == n-1) {
                result++; 
            }
        }
         
        return result; 
    }
}