C++ / 프로그래머스 / 순위

문제

 

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

프로그래머스

문제풀이

 

플로이드 와샬 알고리즘을 통해 문제를 풀었다.

결과인 results에는 [0] 선수가 [1] 선수를 이겼다는 정보가 담겨있다. 그 말은 [1] 선수는 [0] 선수한테 졌다는 의미도 된다.

따라서 두 정보를 벡터를 만들어 저장한다. 이기면 1, 지면 -1로, 상대전적이 없으면 2로 두었다.

자기 자신과 싸울 수는 없으므로 반복문을 통해 [idx][idx] = 0으로 설정한다.

 

A가 B보다 실력이 좋다면 A선수는 B를 항상 이긴다고 되어있다.

그래서 삼단논법을 통해, A가 C를 이기고, C가 B를 이긴다면 A는 B를 이긴다는 것을 알 수 있다.

삼중 반복문을 통해 해당 정보들을 갱신한다.

갱신하게 되면 상대전적이 없는 경우를 제외하고 1 또는 -1로 채워질 것이다. (자기 자신은 0)

상대전적이 없는 경우를 거르기 위해 answer는 선수의 수인 n으로 두고,

조건문을 통해 경기의 결과 값이 2이면 answer에서 값을 하나씩 뺀다.

 

코드

 

#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer(n), A(0), B(0), C(0), idx(0);
    vector<vector<int>>matches(n + 1, vector<int>(n + 1, 2));

    for (idx = 0; idx < results.size(); ++idx) {
        matches[results[idx][0]][results[idx][1]] = 1;
        matches[results[idx][1]][results[idx][0]] = -1;
    }

    for (idx = 1; idx <= n; ++idx) {
        matches[idx][idx] = 0;
    }

    for (C = 1; C <= n; ++C) {
        for (A = 1; A <= n; ++A) {
            for (B = 1; B <= n; ++B) {
                if (matches[A][C] == 1 && matches[C][B] == 1) {
                    matches[A][B] = 1;
                    matches[B][A] = -1;
                }
            }
        }
    }

    for (A = 1; A <= n; ++A) {
        for (B = 1; B <= n; ++B) {
            if (matches[A][B] == 2) {
                answer--;
                break;
            }
        }
    }

    return answer;
}