[프로그래머스][C++] 순위

순위

문제 링크

순위

분석

• n은 선수의 수입니다.
  • one-based indexing으로 이루어져있습니다.
• results는 경기 결과로 2차원 배열입니다.
  • 모든 경기의 결과가 주어지지 않습니다.

경기는 항상 1:1이며, A가 B를 이겼다는 정보가 주어집니다.

어떤 선수가 다른 선수보다 실력이 좋다면, 항상 이깁니다.

주어진 결과만으로 누락된 경기를 추측하여 정확하게 순위를 매길 수 있는 선수가 몇 명인지 알아내어 반환해야합니다.

선수 A가 다른 모든 선수들과의 관계가 명확해야만 정확한 순위를 매길 수 있습니다.
즉, A가 B를 이겼거나(강함) 졌는지(약함) 관계를 모두 알아야합니다.
이는 A를 기준으로 봤을 때, 자신보다 강한 선수들과 약한 선수들의 합이 n - 1명이어야 합니다.

그래프와 플로이드-워셜(Floyd-Warshall) 알고리즘을 활용하여 풀 수 있습니다.

그래프는 방향 그래프를 사용합니다.
정점의 수는 선수 번호만큼 사용하며, 간선의 방향은 경기 결과로 진 사람이 이긴 사람의 방향으로 표현합니다.

풀이

#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    // 그래프를 초기화한다.
    // i 선수가 j에 대해 저장하며, 다음과 같습니다.
    // 1인 경우 i가 j를 이긴 상태, -1인 경우 i가 j에게 진 상태, 0이면 알 수 없는 상태입니다.
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
    
    // 주어진 결과를 저장합니다.
    for (const auto& result : results)
    {
        int winner = result[0];
        int loser = result[1];
        
        graph[winner][loser] = 1;
        graph[loser][winner] = -1;
    }
    
    // 플로이드-워셜 알고리즘으로 간접적인 승패 관계를 추론합니다.
    // i가 k에게 이기고, k가 j에게 이기면 i는 j를 이길 수 있습니다.
    // k는 중간 경유 선수입니다.
    for (int k = 1; k <= n; ++k)
    {
        // i는 시작 선수입니다.
        for (int i = 1; i <= n; ++i)
        {
            // j는 도착 선수입니다.
            for (int j = 1; j <= n; ++j)
            {
                // i가 k에게 이기고, k가 j에게 이기면 i는 j에게 이깁니다.
                if (graph[i][k] == 1 && graph[k][j] == 1)
                {
                    graph[i][j] = 1;
                    graph[j][i] = -1;
                }
                // i가 k에게 지고, k가 j에게 지기면 i는 j에게 집니다.
                else if (graph[i][k] == -1 && graph[k][j] == -1)
                {
                    graph[i][j] = -1;
                    graph[j][i] = 1;
                }
            }
        }
    }
    
    // 각 선수별로 다른 모든 선수와의 슬/패 관계를 알 수 있는지 확인합니다.
    for (int i = 1; i <= n; ++i)
    {
        // 승 혹은 패 관계가 확실하게 있는 선수의 수를 저장합니다.
        int known = 0;
        
        for (int j = 1; j <= n; ++j)
        {
            // 자기 자신과의 관계는 제외합니다.
            if (i == j)
            {
                continue;
            }
            
            // 승패 정보가 존재하면 선수 수를 증가합니다.
            if (graph[i][j] != 0)
            {
                ++known;
            }
        }
        
        // i 선수가 다른 모든 선수와 승패가 황적됐기 때문에 순위를 매길 수 있습니다.
        if (known == n - 1)
        {
            ++answer;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n^3)$입니다.

• 그래프를 초기화 $O(n + 1) \times O(n + 1) \approx O(n^2)$
• 그래프에 값을 저장하는 반복문 $O(m)$
  • m은 경기 결과의 수입니다.
• 플로이드-워셜 알고리즘 $O(n^3)$
• 각 선수가 다른 모든 선수들과의 승/패 여부를 확인하는 반복문 $O(n^2)$
• $O(n^2) + O(m) O(n^3) + O(n^2)$

공간 복잡도는 $O(n^2)$입니다.

• i 선수가 j에 대해 저장하는 그래프 $O(n^2)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.15MB)
테스트 3 〉 통과 (0.01ms, 3.69MB)
테스트 4 〉 통과 (0.02ms, 4.2MB)
테스트 5 〉 통과 (0.08ms, 4.16MB)
테스트 6 〉 통과 (0.16ms, 4.2MB)
테스트 7 〉 통과 (0.59ms, 4.19MB)
테스트 8 〉 통과 (1.51ms, 3.91MB)
테스트 9 〉 통과 (1.82ms, 4.19MB)
테스트 10 〉 통과 (1.65ms, 4.14MB)