[코테연습] 순위

오늘은 그래프 문제를 풀었다.

 

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

프로그래머스

 

해당 문제는 대진표를 2차원 배열로 작성할 수 있는지 여부에 따라서 문제를 풀 수 있었던 것 같다.

 

    1. 순위표를 만든다
        - 2차원 배열
        - [4,3] 의 경우 4번 선수가 승리 / 3번 선수가 패배하였음
            => [4][3] = 1 ( win ) , [3][4] = -1 (win)
    
    2. 해당 순위표에서 교차 win 과 lose 를 구한다
        - 1번 선수는 2번 선수에게 이겼기 때문에, 5번 선수에게 이긴 것 과 같다. [1][2] [2][5] = [1][5]
        - 3번 선수는 2번 선수에게 이겼기 때문에, 5번 선수에게 이긴 것 과 같다. [3][2] [2][5] = [3][5]
        - 4번 선수는 2번 선수에게 이겼기 때문에, 5번 선수에게 이긴 것 과 같다. [4][2] [2][5] = [4][5]
        - 5번 선수는 2번 선수에게 졌기 때문에, 1번 선수와 진 것과 같다. [5][2] [2][1] = [5][1];
        - 5번 선수는 2번 선수에게 졌기 때문에, 3번 선수와 진 것과 같다. [5][3] [2][3] = [5][3];
        - 5번 선수는 2번 선수에게 졌기 때문에, 4번 선수와 진 것과 같다. [5][2] [2][4] = [5][4];

    3. 0번 인덱스를 제외하고 0이 없는 값은 모든 순위가 결정되었기 때문에 해당 값을 구하여 리턴한다.

 

 

 public int solution(int n, int[][] results) {

        int answer = 0;

       

        int[][] map = new int[n+1][n+1];

        for(int i = 1; i <= n; i++) {

            Arrays.fill(map[i], 0);

            map[i][i] = 1;

        }

        for(int[] arr : results) {

            int w = arr[0];

            int l = arr[1];

            map[w][l] = 1;

            map[l][w] = -1;

        }

        print(map);

        for(int k = 1; k <= n; k++) {

            for(int w = 1; w <= n; w++) {

                for(int l = 1; l <= n; l++) {

                    if (map[w][l] != 0) continue;

                    if (map[w][k] == 1 && map[k][l] == 1) {

                        map[w][l] = 1;

                        System.out.println("map["+w+"]["+k+"] && map["+k+"]["+l+"] ==> map["+w+"]["+l+"]");

                    } else if (map[w][k] == -1 && map[k][l] == -1) {

                        map[w][l] = -1;

                        System.out.println("map["+w+"]["+k+"] && map["+k+"]["+l+"] ==> map["+w+"]["+l+"]");

                    }

                }

            }

        }

       

        print(map);

        for(int[] arr : map) {

            int cnt = 0;

            for(int num : arr) {

                if(num!=0) {

                    cnt++;

                }

            }

            if (cnt == n) {

                answer++;

            }

        }

        return answer;

    }