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

문제 링크

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

코딩테스트 연습 - 순위

 

 풀이 과정

 

필자는 이 문제를 보고 순서대로 로직을 정리해봤다.

 

1. 선수별 경기 결과를 인접행렬에 저장한다.
   선수 1이 선수 2를 이긴 경우, graph[1][2] = 1, 선수 2가 선수 1에게 졌으니 graph[2][1] = 0이 들어간다.

2. 주어진 경기 결과로 구현한 인접행렬을 바탕으로 확정된 순위를 구한다.

   선수가 N명일 때, 선수a가 지고, 이긴 경우를 합쳐 N-1인 경우 해당 선수의 순위를 확정지을 수 있다.

   ex) 선수 2의 경우, 이긴 경기 [선수5] + 진 경기[선수1, 3, 4] = 4 = 5-1
        선수 2는 4위를 확정지을 수 있다.
        (이 문제에는 선수의 순위를 구하는것이 아닌, 확정지을 수 있는 순위의 개수를 구하는 것이다.)

3. 선수의 A가 B를 이기면, 항상 A는 B를 이긴다. 따라서 A가 B를 이기고, B가 C를 이긴다면 A는 C를 이길 수 있다.
   이 법칙을 이용해서 선수 별 이기고 지는 경우를 추가한다. (A -> B, B -> C = A -> C)

4. 2번의 경우에 따라 확정지을 수 있는 순위의 개수를 구한다.

 

해당 1~4번 로직을 짜는 것에는 큰 무리까진 없었다. 다만 3번의 경우를 탐색해야 하는 경우에서 상당히 골머리를 앓았다.

따라서 힌트(?)를 조금 얻어 '플루이드-워셜' 알고리즘을 사용 하여 3번을 구현하였다.

 

(해당 알고리즘을 아주 쉽게 정리해놨다. 참고해보자)

https://born2bedeveloper.tistory.com/44

[JAVA] 플로이드-워셜 알고리즘

 

즉, 3번 로직에 따라 A -> B, B -> C면 A -> C 법칙을 사용하기 위해, 선수를 노드로 간주한다면 

각 선수가 모든 선수를 (B의 경우처럼)거쳐가서 간접적으로 이길 경우를 찾는 것이다.

문제 예시를 보면 4번 선수가 2번을 이기고, 2번이 5번을 이겼으니 4번은 5번을 무조건 이기게 된다.

이러한 경우를 찾아내서 graph[4][5] = 1처럼 인접행렬에 더 많은 경기결과를 추가하는 것이다.

 

 코드 구현

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] graph = new int[n+1][n+1];
        
        for(int i = 0; i < results.length; i++) 
            graph[results[i][0]][results[i][1]] = 1; //이김
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= n; j++) {
                for(int z = 0; z <= n; z++) {
                    if (graph[j][i] == 1 && graph[i][z] == 1)
                        graph[j][z] = 1;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            int game = 0;
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] == 1 || graph[j][i] == 1)
                    game++;
            }
            if (game == n-1)
                answer++;
        }
        return answer;
    }
}

사실, 이번 문제를 통해 플로이드-워셜 알고리즘을 새로 접할 수 있었다.

시간 복잡도가 O(N^3)이긴 하나, 입력 범위가 크지 않다면 짧은 코드로 거쳐가는 최단경로를 쉽게 알 수 있으므로 이와 비슷한 문제가 나왔을 때 유용하게 사용할 것 같다.