[프로그래머스 JAVA] 순위

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

프로그래머스

 

---

문제 접근 방법

 

위상 정렬

위상 정렬로 열내면서 풀어봤지만 문제를 풀수록 미궁 속으로 빠졌다. 위상 정렬로 풀이하면 처음과 끝에 있는 선수들의 순위는 비교적 쉽게 정할 수  있지만, 중간에 있는 선수들의 순위는 모호하고, 접근하기 까다로워진다. 

문제를 풀면서 이상하다고 생각해서 찾아보니 위상 정렬은 순서가 명확히 정해진 상황에서 사용하는 게 올바르다고 한다.
(순서가 명확, 사이클X -> 위상 정렬)

 

플로이드 와샬

A가 B와의 승부결과가 있고, B가 C와의 승부결과가 있다면 A와 C의 승부결과를 도출할 수 있다고 생각했지만, 이는 틀렸다.

A가 B에게 (1)승리(2)패배하고, B가 C에게 (1) 승리(2) 패배한다면, A가 C에게 (1) 승리(2) 패배하는 것이었다.

즉, (1)과 (2)는 섞여서는 안 된다는 것이다. 친구 이름 넣어서 예시를 들어본다면 더 이해가 잘된다 ㅋㅋ...

 

결론적으로

1. 초기 입력값으로 인접 행렬(2차원 배열)을 만들고,
(초기값:0, 승: 1, 패: -1)

2. 플로이드 와샬 알고리즘으로 인접 행렬을 채운다.
if (adjMat[A][B] == 1 && adjMat[B][C] == 1) {
    adjMat[A][C] = 1
    adjMat[C][A] = -1
}

(이때, 1과 -1이 교체될 수 있다. 몇 번이나 수정하며 비교해 봤지만 위 조건식이 제일 빠르더라...)

3. 인접 행렬에서 바뀌지 못한 값이 있다면 (순위가 명확하지 않다면),
if(adjMat[i][j] == 0)

4. answer에서 1씩 뺀다. (answer의 초기값은 선수 총원: n)

 

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

        int[][] adjMat = new int[n + 1][n + 1];
        for (int[] r : results) {
            int winner = r[0];
            int loser = r[1];

            adjMat[winner][loser] = 1;
            adjMat[loser][winner] = -1;
        }

        for (int mid = 1; mid <= n; mid++) {
            for (int start = 1; start <= n; start++) {
                for (int end = 1; end <= n; end++) {
                    // 여기서 여러가지 조건으로 최적화할 수 있음
                    if (adjMat[start][end] != 0) continue;

                    if (adjMat[start][mid] == 1 && adjMat[mid][end] == 1) {
                        adjMat[start][end] = 1;
                        adjMat[end][start] = -1;
                    }
                }
            }
        }

        // for(int i=1;i<=n;i++){
        //     for(int j=1;j<=n;j++){
        //         System.out.print(adjMat[i][j] + " ");
        //     }
        //     System.out.println();
        // }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue; // 자신과의 승부
                if (adjMat[i][j] == 0) {
                    answer--;
                    break;
                }
            }
        }

        return answer;
    }
}

 

---

결론

 

문제가 생각보다 쉬워서 허무하다. 위상 정렬로 풀다가 진이 빠져서 어려운 문제라고 생각했던 것 같다.