문제

Programmers Lv3, 순위

핵심

• 입력의 크기가 100이라 대략 $O(N^3)$이하 알고리즘을 사용한다.
• 초기 접근 방법은 순서를 구하는 것으로 생각하여 위상 정렬을 사용하였다.
  1. 위상정렬로 순서 구함.
  2. 1번에서 나온 순서로 다시 노드를 돌면서 순서 검증
• 하지만 위상 정렬로 구한 순서를 가지고, 정확한 순서를 구하고 싶었지만, 이를 위한 추가 정보를 얻어낼 수 없었다. 즉, 위상 정렬은 모순되지 않는 순서를 구할 수는 있지만 정확한 순서를 구하는 데 사용하는 알고리즘은 아니다.
• 두 번째 접근 핵심 아이디어는 정확한 순위를 알아내기 위해선 모든 사람과 경기(n - 1)를 해야 한다는 사실이다. 그렇다면, 예제 입력 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]일 때, 2번은 4번 경기를 했기에 정확한 순서를 알 수 있다. 5번은 데이터로는 1번만 경기를 했지만, 모든 경기를 참석한 2번에게 졌기 때문에 확실한 순서를 알 수 있다.
• 즉, 5번은 2번을 이긴 사람에게 졌다고 표시를 하면 된다. 이 경우 플루이드 워샬 알고리즘을 활용할 수 있다. 특정 경유지를 거칠 때 최단거리를 갱신하는 로직을 A가 B에게 이길 때, B가 C를 이겼다면 A도 C를 이긴다고 표시하는 로직으로 재활용할 수 있는 것이다.

    for (auto& e: results) {
        ret[e[0]][e[1]] = 1;
        ret[e[1]][e[0]] = -1;
    }

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

i가 k한테 이기고, k가 j에게도 이기면 i가 j를 이긴다는 것이다. 반대로 i가 k한테 지고, k가 j한테 지면 i는 j에게도 진다는 것이다.

• 위처럼 경기 횟수를 채워주고, 모든 사람과 경기를 치뤄 순위가 확실해진 사람의 개수를 세어 반환하면 된다.

개선

코드

C++

#include <string>
#include <vector>
#include <iostream>

using namespace std;
    
int ret[104][104];
int solution(int n, vector<vector<int>> results) {
    
    for (auto& e: results) {
        ret[e[0]][e[1]] = 1;
        ret[e[1]][e[0]] = -1;
    }

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

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;
        for (int j = 1; j <= n; ++j) {
            if (ret[i][j]) ++cnt;
        }
        if (cnt == n - 1)
            ++ans;
    }

    return ans;
}

Java

class Solution {
    
    int[][] ret = new int[104][104];
    
    public int solution(int n, int[][] results) {
        
        for (var e : results) {
            ret[e[0]][e[1]] = 1;
            ret[e[1]][e[0]] = -1;
        }

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

        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int cnt = 0;
            for (int j = 1; j <= n; ++j) {
                if (ret[i][j] != 0) {
                    ++cnt;
                }
            }
            if (cnt == n - 1) {
                ++ans;
            }
        }

        return ans;
    }
}