[프로그래머스] 순위 (JAVA)

[풀이]

문제는 각 선수 간의 경기 결과를 통해 명확히 순위를 알 수 있는 선수의 수를 구하는 것이다.

플로이드 워셜 알고리즘을 이용해 모든 선수 간의 관계를 구하고, 승패 관계를 기반으로 순위를 계산해준다.

 

아래 3단계를 통해 순위를 알 수 있는 선수의 수를 구했다.

 

1. 승패 관계 초기화

• graph 라는 2차원 배열을 선언해 선수 간의 승패 여부를 관리
• i가 j를 이기면 graph[i][j]가 1, 지면 graph[i][j]가 -1

2. 플로이드 워셜 알고리즘

• 중간 노드를 거쳐 갈 수 있는 승패 관계를 업데이트 한다.
• 예를 들어, A → B, B → C라면 A → C 관계를 유추할 수 있다.

3. 순위 확정

• 한 선수에 대해 승리한 선수와 패배한 선수의 합이 n-1이면 해당 선수의 순위를 알 수 있다.

 

 

 

[코드]

class Solution {
    public int solution(int n, int[][] results) {
        int[][] graph = new int [n+1][n+1];
        int answer = 0;
        for(int [] res : results) {
            int winner = res[0];
            int loser = res[1];
            graph[winner][loser] = 1;
            graph[loser][winner] = -1;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][k] == 1 && graph[k][j] == 1) {
                        graph[i][j] = 1;
                    } else if (graph[i][k] == -1 && graph[k][j] == -1) {
                        graph[i][j] = -1;
                    }
                }
            }
        }

        for(int i=1;i<=n;i++){
            int cnt=0;
            for(int j=1;j<=n;j++){
                if(graph[i][j] == 1 || graph[i][j] == -1)   cnt++;
            }
            if(cnt == n-1)  answer++;
        }
        return answer;
    }
}

 

[문제]

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

프로그래머스