[그래프] 순위 - Java코드

https://programmers.co.kr/learn/courses/30/lessons/49191?language=java 

코딩테스트 연습 - 순위

 

문제

 

 

문제 이해

입출력 설명에 집중할 필요가 있다.

문제가 실질적인 경기와 다르게 계산된다.

승패라기보다 절대적 전투력 정도로 생각해야 될 것같다.

 

먼저 A->B , B->C이면 A->C도 성립한다.

 

설계

질문하기란에서 보니 다엑스트라, 플로이드 워셜 알고리즘을 쓴다는 말이 많지만,

모르니깐 원초적인 접근으로 풀어보겠다.

 

승패여부를 기록할 NxN 크기의 매트릭스를 만들어서 승 1 , 패 -1  자신은 0으로 초기화해준다.

ex> n=5, results = [[1,2],[1,3],[1,4],[2,3],[3,4]]

[ 0  1  1  1  0 ] 
[-1  0  1  0  0 ] 
[-1 -1  0  1  0 ] 
[-1  0 -1  0  0 ] 
[ 0  0  0  0  0 ] 

이런식으로 셋팅해준다

 

그리고 1번부터 승리한 선수의 승정보를 가져와 수정하고,

패배한선수에게 가서 나의 승리정보를 전달해줘야한다.

 

(나한테 진사람에게 진사람들은 나를 못이기고, 내가 이긴사람은 그사람이 이긴사람들도 내가 다 이긴다.)

 

이러한 규칙으로 매트릭스를 순회하며 승패여부를 기록해주고,

결과적으로 0이 하나인 사람을 count하여 반환한다 

참고

 

풀이

class Solution {
    static int [][] matrix;
    public int solution(int n, int[][] results) {
        // 0 초기화
        matrix = new int [n][n];
        for(int i=0; i<n;i++)	for(int j=0; j<n; j++) matrix[i][j]=0;
        // 승패 기록
        for(int[] a : results)	update(a[0]-1,a[1]-1);
        // 승리한 사람의 승리정보 가져와 update
        for(int i=0; i<n;i++) {
            for(int j=0; j<n; j++) {
                if(matrix[i][j]==1) {
                    for(int k=0;k<n;k++)
                        if(matrix[j][k]==1)
                            update(i,k);
                }else if(matrix[i][j]==-1){
                    for(int k=0;k<n;k++)
                        if(matrix[i][k]==1)
                            update(j,k);
                }
            }
        }
        int sum,answer=0;
        for(int[] a : matrix) {
            sum=0;
            for(int b : a) {
                if(b==0) sum+=1;
            }
            if(sum==1)
                answer+=1;
        }

        return answer;
    }
    public static void update(int i, int j) {
        matrix[i][j] = 1;
        matrix[j][i] = -1;
    }
}