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

• 문제 링크
• 참고 : 플로이드-워셜 알고리즘

풀이 과정

• Floyd-Warshall 알고리즘을 되짚어보고 진행하면 수월하다.

• 문제에 주어지는 조건 (선수의 수 및 전적)을 int 형 2차원 배열로 표현할 수 있다. 주어진 예제라면 아래 표와 같이 표현된다.
  

  

  • int 타입 2차원 배열로 표현하였으므로 위 표의 빈칸도 0으로 초기화되어있다.
    • 따라서, 0은 자기 자신 또는 결과 모름을 의미한다.
  • 1은 상대에게 승리했음을, -1은 상대에게 패배했음을 의미한다.

• 이후 1번 선수부터 아래의 과정을 반복한다.

  1. i번 선수가 승리한 상대 선수를 찾는다. 주어진 예제에서는 1번 선수가 2번 선수를 상대로 승리했다.
  2. 1번의 결과로 찾은 선수가 승리한 상대 선수를 찾는다. 주어진 예제에서는 2번 선수가 5번 선수를 상대로 승리했다.
  3. 1번의 결과로 찾은 선수가 2번의 결과로 찾은 선수를 상대로 이겼다고 기록한다.

• 위 과정을 모든 선수에 대해서 반복하면 최종 대진 결과가 적힌 표를 얻을 수 있다. 문제의 예제라면 아래의 표와 같이 갱신된다.
  

  

• 최종 결과가 적힌 표를 가지고 다시 전체 선수에 대해 순회하며 0이 아닌 결과의 수를 센다. 이 결과가 n - 1이라면 순위를 알 수 있다.

Code

import java.util.Arrays;

class Solution {
    public int solution(int n, int[][] results) {
        int[][] matchResults = new int[n][n];

        // setup
        for (int[] result : results) {
            int winner = result[0] - 1;
            int loser = result[1] - 1;
            matchResults[winner][loser] =  1; // win
            matchResults[loser][winner] = -1; // lose
        }

        // a → b 이고 b → c 이면 a → c
        for (int b = 0; b < n; b++) {
            for (int a = 0; a < n; a++) {
                if (matchResults[a][b] <= 0) { // a가 b에게 이긴 경우에만 진입
                    continue;
                }

                for (int c = 0; c < n; c++) {
                    if (matchResults[b][c] > 0 && matchResults[a][c] == 0) {
                        // a가 c를 이겼는지는 아직 모를 때, b가 c에게 이겼으면
                        matchResults[a][c] = 1; // a도 c에게 승리
                        matchResults[c][a] = -1;
                    }
                }
            }
        }

        int answer = 0;
        for (int[] matchResult : matchResults) {
            answer += (int) Arrays.stream(matchResult).filter(result -> result != 0).count() == (n - 1) ? 1 : 0;
        }

        return answer;
    }
}

결과