[프로그래머스] 순위

1. my sol

#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>

using namespace std;
vector<int> done(4500,0);
vector<int> l(4500,0);
vector<int> sum(4500,0);

void proc(    map<int, set<int>> m)
{   
    for(auto i : m)
    {        
        int cnt = 0 ;
        cnt += i.second.size();
        if(done[i.first]!=2)
            done[i.first] = cnt>0 ? 0 : 1;
    }
}
bool empty_all(    map<int, set<int>> inv_map)
{   
    bool b = true;;
    for(auto i : inv_map)
    {        
        int cnt = 0 ;
        cnt += i.second.size();
        if(cnt>0) b = false;
    }
    return b;
}
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for(int p = 0 ; p < 2 ; p ++)
    {
            map<int, set<int>> m;
            map<int, set<int>> inv_map;
            done = vector<int> (4500,0);
            l = vector<int> (4500,0);

            for(int i = 1 ; i <= n ; i ++)
                {m[i]={}; inv_map[i] = {};}
            for(auto r : results)
            {
                m[r[0+p]].insert(r[1-p]);
                inv_map[r[1-p]].insert(r[0+p]);
                l[r[0+p]] ++;    
            }
            proc(m);
            while(!empty_all(inv_map))
            {
                int done_idx = find(done.begin(), done.end(), 1) - done.begin();
                done[done_idx] = 2;
                set<int> inv = inv_map[done_idx];
                for(auto i : inv)
                {
                    for(auto add : m[done_idx])
                    {
                        m[i].insert(add);
                    }
                    inv_map[done_idx].erase(i);
                    l[i] --;
                    if(l[i]==0)
                        done[i] = 1;
                }

            }

            for(int i = 1 ; i <= n ; i ++)
            {
                sum[i]+=m[i].size();
            }
        }


    for(int i = 1 ; i <= n ; i ++)
        if(sum[i]==n-1) answer++;
    return answer;
}

int main()
{
    vector<vector<int>> results = {{4,3},{4,2},{3,2},{1,2},{2,5}};
    cout<<solution(5,results)<<endl;
}

p = 0 => 자기(n)보다 아랫 순위의(L(n)) 사람을 정리

p =1  => 자기(n)보다 윗 순위의(U(n)) 사람을 정리

 

1)

L(1) = 2, L(2)

L(2) = 5, L(5)

L(3) = 2, L(2)

L(4) = 2, L(2), 3, L(3)

L(5) = empty;

 

=> L(5)가 done이므로 L(2)를 done할 수 있음

2)

L(1) = 2, L(2)

L(2) = 5

L(3) = 2, L(2)

L(4) = 2, L(2), 3, L(3)

L(5) = empty;

=>

L(2)가 done 이므로

L(1), L(3). L(4)를 갱신 할 수 있음 

이때 L(1), L(3)은 done이지만 L(4)는 아님

 

3)

L(1) = 2, 5

L(2) = 5

L(3) = 2, 5

L(4) = 2, 5, 3, L(3)

L(5) = empty;

=>

4) 

L(1) = 2, 5

L(2) = 5

L(3) = 2, 5

L(4) = 2, 5, 3

L(5) = empty;

 

같은방식으로 U(n)정리 후 위 아래 합이 n-1인 경우 순위를 알 수 있다.

 

2) Floyd-Warshall algorithm

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

using namespace std;
bool m[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for(auto row : results)
        m[row[0]][row[1]]=1;

    for(int j = 0 ; j < n ; j ++)
        for(int i = 0 ; i < n ; i ++)
            for(int k = 0 ; k < n ; k ++)
                if(m[i][j] && m[j][k])
                    m[i][k]=1;
    
    for(int r = 0 ; r < n ; r ++)
        {
            int s = 0 ;
            for(int c = 0 ; c < n ; c++)
                s+= m[r][c] + m[c][r];
            if(s==n-1)
             answer++;
        }

    return answer;
}
int main()
{
    vector<vector<int>> results = {{4,3},{4,2},{3,2},{1,2},{2,5}};
    cout<<solution(5,results)<<endl;
}

 

어메이징하다.

거쳐가는 node를 가장 outer 로 하여 삼중 for loop를 통해

graph 전체의 from->to 관계를 구하는 Floyd-Warshall 알고리즘을 기억하자.