프로그래머스 - 순위

프로그래머스 - 순위

옛날에 DFS로 괜히 어렵게 풀어서 엄청 오래걸렸길래 다시 풀었다. (거의 10000ms 걸리지만 통과는 함)

a, b를 기준으로 a는 승자 b는 패자이다. 또한 b는 a가 졌던 사람들에게도 진다. 반대로 a는 b가 이겼던 사람들에게 이긴다.

이를 set을 이용해서 a를 기준으로 a를 이기는 승자들에 대해서는 a가 이겼던 패자들을 set에 포함시켜주고, 반대로 a가 이겼던 패자들에 대해서는 a를 이기는 승자들을 set에 포함시켜주면 된다. (중복 방지로 set)

코드는 다음과 같다.

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

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<set<int>> win(n + 1);
    vector<set<int>> lose(n + 1);
    for(auto it : results) {
        win[it[0]].insert(it[1]);
        lose[it[1]].insert(it[0]);
    }
    for(int i=1;i<=n;i++) {
        /*
         *   i 번째의 승자와 패자에 대해서 동시에 업데이트해줘야 
         *   i + 1번째를 업데이트할 때 빠짐없이 할 수 있음
         */
        for(auto it : win[i]) 
            for(auto itt : lose[i]) 
                lose[it].insert(itt);    
        
        for(auto it : lose[i]) 
            for(auto itt : win[i]) 
                win[it].insert(itt);
    }
    
    for(int i=1;i<=n;i++)
        if(win[i].size() + lose[i].size() == n - 1)
            answer++;
    
    return answer;
}