[Lv.3] 프로그래머스 - 순위 : Java

프로그래머스

 

 

 

이해하기

처음엔 문제도 이해가 안 됐다 ㅋㅋ...

예시로 설명하자면 5명의 권투 선수가 대회에 참여했고, 이들의 경기 결과가 result 배열로 주어진다.

[4, 3]은 4번 선수가 3번 선수를 이겼다는 뜻이다.

 

예시를 정리하면 이런 형태가 된다.

n행 n열 배열인데, 해당 행의 선수가 해당 열의 선수를 이겼다는 뜻이다.

 

이 문제의 포인트는 이들의 경기 결과가 서로 연결된다는 점이다.

만약 4번 선수가 3번 선수를 이겼고, 3번 선수가 2번 선수를 이겼다면 4번 선수는 2번 선수도 이긴 것으로 한다.

 

 

경기 결과를 전부 연결해주면 이런 형태가 된다.

이 중 경기 결과가 4개인 경우에만 자기 자신의 순위를 알 수 있다.

(e.g. 1번 선수는 2번, 3번, 4번, 5번과 경기를 치루니 총 4회)

 

위 그래프에서 행과 열을 살폈을 때 경기의 수가 4인 경우를 찾으면 된다.

2번 선수는 1번 선수한테 지고, 5번 선수한테 이기고, 3번 선수한테 지고, 4번 선수한테 졌으니 경기는 총 4번 치룬다.

5번 선수는 1, 2, 3, 4번 선수한테 졌으니 경기는 총 4번 치룬 것이다.

 

따라서 순위를 알 수 있는 사람은 2번 선수와 5번 선수 2명이다.

 

참고한 블로그⬇️

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

 

 

문제풀이

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

        for (int i = 0; i < results.length; i++) {
            graph[results[i][0] - 1][results[i][1] - 1] = 1;
        }

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

        for (int i = 0; i < n; i++) {
            int count = 0;

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

            if (count == n - 1) {
                answer++;
            }
        }

        return answer;
    }
}

 

int answer = 0;
        int[][] graph = new int[n][n];

        for (int i = 0; i < results.length; i++) {
            graph[results[i][0] - 1][results[i][1] - 1] = 1;
        }

 

경기 결과를 저장할 2차원 배열 graph를 만든다.

for문을 돌며 경기 결과를 저장한다. (이 때 graph는 0부터 시작하니 -1씩 해준다.)

 

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

 

j가 i를 이겼고, i가 k를 이겼다면 j도 k를 이긴것으로 해주는 삼중 for문이다.

 

        for (int i = 0; i < n; i++) {
            int count = 0;

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

            if (count == n - 1) {
                answer++;
            }
        }

 

for문을 돌며 각 선수의 경기 횟수를 count한다.

count가 n - 1이라면 해당 선수는 순위를 알 수 있으니 answer++ 해준다.

 

 

어려웠지만 정리해보니 이해가 된다.