Post

[Programmers] #49191 - 순위 [Java][C++][Python]

[Programmers] #49191 - 순위 [Java][C++][Python]

문제 링크


1. 아이디어

일부 경기 결과만 주어졌을 때 순위를 정확히 알 수 있는 선수가 몇 명인지 세는 문제다. 선수들의 승패를 이긴 선수에서 진 선수로 가는 간선으로 보면, 실력이 좋은 선수는 항상 이기므로 A 선수가 B 선수를, B 선수가 C 선수를 이겼을 때 A 선수가 C 선수보다 실력이 좋아 직접 붙지 않았어도 A 선수가 C 선수를 이긴다고 알 수 있다. 즉 한 선수가 다른 선수를 이긴다고 알 수 있는 것은 이긴 선수에서 진 선수까지 간선을 따라 닿을 수 있는 것과 같고, 모든 선수 쌍의 도달 여부는 플로이드-워셜 알고리즘으로 구한다. $O(n^3)$이지만 $n \le 100$이라 충분하다.

순위를 구할 한 선수(기준 선수)의 순위는 그 선수보다 실력이 좋은 선수의 수에 1을 더한 값이다. 기준 선수를 이긴다고 알 수 있는 선수는 반드시 앞에, 기준 선수에게 진다고 알 수 있는 선수는 반드시 뒤에 서고, 승패를 알 수 없는 선수는 앞에 서는 선수를 이길 수도 뒤에 서는 선수에게 질 수도 없어(그랬다면 기준 선수와의 승패도 알 수 있다) 기준 선수의 앞에 서든 뒤에 서든 구한 승패와 모순이 없다. 그러므로 승패를 알 수 없는 선수가 있으면 그 선수들을 모두 뒤에 세운 순위와 모두 앞에 세운 순위가 달라 순위가 하나로 정해지지 않고, 기준 선수가 나머지 $n - 1$명 모두와 승패를 알 수 있을 때만 순위가 하나로 정해지므로 그런 선수의 수가 답이다.


2. 코드

풀이 [Java][C++][Python]

경유지 k를 가장 바깥 반복에 두었다. 안쪽에 두면 k를 거쳐야 이어지는 승패를 놓치는 경우가 생긴다.

승패를 세는 반복은 j가 i와 같은 경우도 훑었지만, 경기 결과에 모순이 없어 dp[i][i]는 참이 되지 않으므로 n - 1과 비교해도 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int solution(int n, int[][] results) {
        boolean[][] dp = new boolean[1 + n][1 + n];
        for (int[] r : results) {
            dp[r[0]][r[1]] = true;
        }

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

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

            if (cnt == n - 1) ans++;
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1 + 100;
bool dp[MAX_N][MAX_N];

int solution(int n, vector<vector<int>> results) {
    for (auto& r : results) dp[r[0]][r[1]] = true;

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

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

        if (cnt == n - 1) ans++;
    }

    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, results):
    dp = [[False] * (1 + n) for _ in range(1 + n)]
    for u, v in results:
        dp[u][v] = True

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if dp[i][k] and dp[k][j]:
                    dp[i][j] = True

    ans = 0
    for i in range(1, n + 1):
        cnt = 0
        for j in range(1, n + 1):
            if dp[i][j] or dp[j][i]:
                cnt += 1

        if cnt == n - 1:
            ans += 1

    return ans

This post is licensed under CC BY 4.0 by the author.