[프로그래머스 Level3] 순위 c++

문제

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

코딩테스트 연습 - 순위

 

문제 풀이

1. 정확하게 순위를 매길 수 있다는건 이길 수 있는 선수의 수와 만나면 지는 선수의 수를 안다는 것이고, 이들을 합했을 때 자신을 제외한 N-1명이라는 것입니다.

 

2. 모든 선수간의 승,패 관계의 관계는 N<=100이므로 플로이드 와샬 알고리즘을 사용해 알아낼 수 있습니다.

 

3. 선수간의 승, 패관계를 이미 아는 경우를 제외하고, 기존의 관계를 통해 새로운 관계를 알아낸 경우 (ex :  u > v 이고 v > w 이면 u > w) 각 선수의 이길 수 있는 선수의 수와 만나면 지는 선수의 수를 하나씩 올려주면됩니다.

 

코드

#include <string>
#include <vector>

using namespace std;

int in[101],out[101]; // in[i] : i번 선수가 만나면 지는 선수의 수, out : i번 선수가 이길수 있는 선수의 수
bool c[101][101]; // c[u][v] : u번 선수가 v번선수를 이김 

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for (int i = 0 ; i < results.size() ; i++) {
        c[results[i][0]][results[i][1]] = 1;
        out[results[i][0]]++, in[results[i][1]]++;
    }
    for (int k = 1 ; k <= n; k++){
        for (int i = 1 ; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (c[i][j]) continue; // 승,패 관계를 이미 아는 경우
                if (c[i][k] && c[k][j]){
                    c[i][j] = 1; 
                    out[i]++, in[j]++; 
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (in[i] + out[i] == n - 1) answer++;
    return answer;
}

 

비슷한 문제

https://www.acmicpc.net/problem/10159