풀이

i번 선수를 이긴 선수의 명단인 win과 i번 선수에게 진 선수의 명단인 lose를 만든다.

그리고 results를 확인해서 A가 B에게 이기면 B번 선수의 이긴명단에 A를, A번 선수에게 진 명단에 B를 추가한다.

set<int>win[101];
set<int>lose[101];


for(auto i : results){
  win[i[1]].insert(i[0]);
  lose[i[0]].insert(i[1]);
}

input : [4, 3]

4는 3에게 이겼으므로 win[3]에 4를 추가한다.

3은 4에게 졌으므로 lose[4]은 3를 추가한다.

	1	2	3	4	5
win			4
lose				3

input : results

	1	2	3	4	5
win		4, 3, 1	4		2
lose	2	5	2	3, 2

그리고 위 표에서 2번을 보면

4, 3, 1 > 2 > 5다.

그래서 lose[4], lose[3], lose[1]에 2와 5를 추가해줄 수 있다. (이때 2는 표를 만들때 이미 추가되었으므로 5만 추가해줘도 된다.)

마찬가지로 win[5]는 4, 3, 1을 추가해줄 수 있다.

1번부터 n번까지 위의 과정을 수행한다.

for (int i = 1; i <= n; i++) {
	for (auto j : lose[i]) {
		for (auto k : win[i]) {
			win[j].insert(k);
		}
	}
	for (auto j : win[i]) {
		for (auto k : lose[i]) {
			lose[j].insert(k);
		}
	}
}

	1	2	3	4	5
win		4, 3, 1	4		2, 4, 3, 1
lose	2, 5	5	2, 5	3, 2, 5

이제 위의 표에서 win과 lose의 원소 개수 합이 n-1인것은 확실히 순위를 알 수 있는 선수다.

구현

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

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;

    int rank[101] = {0}; // 디버깅용, i번 선수의 순위
    set<int>win[101]; // i번 선수를 이긴 선수들
    set<int>lose[101]; // i번 선수에게 진 선수들
    
    
    for(auto i : results){
        win[i[1]].insert(i[0]);
        lose[i[0]].insert(i[1]);
    }
    
     for(int i=1;i<=n;i++){
        for(auto j : lose[i]) {
            for(auto k : win[i]){
                win[j].insert(k);
            }
        }
        for(auto j : win[i]) {
            for(auto k : lose[i]){
                lose[j].insert(k);
            }
        }
     }
    for(int i=1;i<=n;i++){
        if(win[i].size() + lose[i].size() == n-1){
            //rank[i] = win[i].size() + 1;
            answer++;
        }
    }
    
    //for(int i=1;i<6;i++) cout<<rank[i]<<" ";
    
    return answer;
}