[프로그래머스] 순위 Java

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

문제 요약

 n명의 권투선수가 서로 시합을 하는데 시합에는 변수가 없기 때문에 A선수가 B선수보다 강하면 A선수가 무조건 이긴다. 경기 결과 몇개가 2차원 배열로 주어질 때 순위를 확실히 알 수 있는 선수의 수를 반환하는 함수를 만들어야 한다.

 

문제 풀이

이 문제의 핵심은 자신에게 진 선수에게 진 선수는 자신에게도 지며, 자신에게 이긴 선수에게 이긴 선수는 자신에게도 이긴다는 것이다. 당연히 동점은 없으므로 타 선수들간의 전적을 모두 알고있는 선수의 수를 반환하는 게 정답이었다.  처음에는 Fighter 클래스를 만들어서 BFS 탐색하였고 정답처리가 나왔으나 너무 시간이 많이 걸리는 방식이었다.

 

 다른 분들의 풀이를 본 결과 이 문제는 플로이드 와샬 알고리즘을 사용해서 풀면 간단하게 풀 수 있는 문제였다. 플로이드 와샬 알고리즘을 사용하는 루프를 통해 승리 전적을 채우고 자신이 승리한 선수와 자신을 승리한 선수의 수의 합이 n-1인 선수 수를 세서 반환하면 된다.

 

 무턱대고 BFS를 썼다가 괜히 시간만 잡아먹고 효율은 잡지 못한 문제였다. 플로이드-와샬 알고리즘을 제대로 숙지해서 다음부터는 이렇게 헤메는 일이 없도록 해야겠다.

 

나의 코드

class 순위 {
    public int solution(int n, int[][] results) {
        int answer = 0;

        /* 승리 전적표 채우기 */
        boolean[][] map = new boolean[n + 1][n + 1];
        for (int[] i : results)
            map[i[0]][i[1]] = true;

        /* 플루이드 와샬 알고리즘을 통해 승리 채우기 */
        for (int k = 1; k <= n; ++k) { // 가운데 선수
            for (int i = 1; i <= n; ++i) { // 강한 선수
                for (int j = 1; j <= n; ++j) { // 약한 선수
                    if (map[i][k] && map[k][j]) {
                        map[i][j] = true;
                    }
                }
            }
        }

        /* 모든 전적을 알 수 있는 선수의 수 구하기 */
        for (int i = 1; i <= n; ++i) {
            boolean possible = true;
            for (int j = 1; j <= n; ++j) {
                if (i != j && !map[i][j] && !map[j][i]) {
                    possible = false;
                    break;
                }
            }
            answer = possible ? answer + 1 : answer;
        }

        return answer;
    }
}