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

[프로그래머스] L3 순위

[풀이]

 

이 문제를 스스로 풀지 못했다면 백준 2458번 키순서로 다시 풀어보시는 걸 추천드립니다.

본 문제는 플로이드 워샬 문제이다.

 

- 입력 -

n=5

result = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

 

[ 초기화 방법 

n x n 크기인 2차원 배열

4는 3을 이긴다 → map[4][3] = 1

3은 4에게 진다 → map[3][4] = -1

 

초기화한 2차원 배열을 경유지 k를 이용해서 아래 조건을 확인하며 배열을 확인한다.

'i가 k에게 이기고 k가 j에게 이길 때, i는 j에게 이긴다' => map[i][k] == 1 && map[k][j] == 1, map[i][j] = 1

'i가 k에게 지고 k가 j에게 질 때, i는 j에게 진다' => map[i][k] == -1 && map[k][j] == -1, map[i][j] = -1

초기 상태 -> 조건에 따라 확인 후

이차원 배열을 돌면서 임의의 A행에 대해 (A, A)가 0인 경우를 제외하고 더 이상 0이 존재하지 않을 경우

해당 행은 순위를 확인할 수 있다. 따라서 결과에 추가해준다.

 

 

class Solution {
    public int solution(int n, int[][] res) {
        int[][] map = new int[101][101];
        
        for(int i=0; i<res.length; i++){
            map[res[i][0]][res[i][1]] = 1; // A[0]가 B[1]를 이김
            map[res[i][1]][res[i][0]] = -1;
        }
        
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(i==j) continue;
                    if(map[i][k] == 1 && map[k][j] == 1) map[i][j] = 1;
                    if(map[i][k] == -1 && map[k][j] == -1) map[i][j] = -1;
                }
            }
        }
        int answer = 0;
        for(int i=1; i<=n; i++){
            boolean check = true;
            for(int j=1; j<=n; j++){
                if(i!=j && map[i][j] == 0){
                    check = false;
                    break;
                }
            }
            answer += (check ? 1 : 0);
        }
        return answer;
    }
}