[프로그래머스] 순위

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

프로그래머스

 

프로그래머스 코딩 테스트 고득점 Kit에 포함된 Level 3 그래프 문제입니다.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int preN, nxtN;
vector<int> AL[101], reverseAL[101];
queue<int> q;

int getPreN(int r){
    int res = 0;
    vector<bool> vis(101);
    q.push(r);
    vis[r] = 1;
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        for(int nxt : reverseAL[curr]){
            if(!vis[nxt]){
                vis[nxt] = 1;
                ++res;
                q.push(nxt);
            }
        }
    }
    return res;
}

int getNxtN(int r){
    int res = 0;
    vector<bool> vis(101);
    q.push(r);
    vis[r] = 1;
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        for(int nxt : AL[curr]){
            if(!vis[nxt]){
                vis[nxt] = 1;
                ++res;
                q.push(nxt);
            }
        }
    }
    return res;
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for(vector<int> result : results){
        int a = result[0]; 
        int b = result[1];
        AL[a].push_back(b);
        reverseAL[b].push_back(a);
    }
    
    for(int i = 1; i <= n; ++i){
        preN = getPreN(i);
        nxtN = getNxtN(i);
        if(preN + nxtN == n-1) ++answer;
    }
    
    return answer;
}

 

정확하게 순위를 매길 수 있는 경우는 다음과 같습니다.

자신의 앞에 있는 선수의 수 + 자신의 뒤에 있는 선수의 수 = (전체 선수의 수 - 1)

 

따라서 주어진 결과를 토대로 두 가지 그래프를 모델링합니다. AL은 뒤에 있는 선수를 세기 위한 directed graph이고 reverseAL은 앞에 있는 선수를 세기 위한 directed graph입니다. 

 

이를 이용해서 각 선수를 root로 해서 BFS를 하면 각 선수의 앞에 있는 선수의 수, 뒤에 있는 선수의 수를 구할 수 있습니다.

 

프로그래머스 문제를 풀면서 아쉬운 점이 시간복잡도 면에서 내가 설계한 알고리즘이 최적화된 알고리즘인지 확인할 길이 없다는 것입니다. BOJ의 경우 시간제한이 보통 1초로 설정되어 있고 입력값에 따라 어느 정도의 시간복잡도를 가지는 알고리즘을 설계해야 할지 가늠이 가능합니다. 반면, 프로그래머스는 지금까지 난이도가 쉬운 문제를 풀어와서 그런 것인지 모르겠지만 입력값이 상대적으로 작은 편이고 테스트케이스도 적은 편이라 구현이 정확하면 대부분 AC를 받는다는 점에서 아쉽습니다. 

 

각 선수를 root로 해서 매번 BFS를 돌리는 대신, 각각 단 한 번의 BFS를 통해 선수마다 앞에 있는 선수의 수, 뒤에 있는 선수의 수를 구할 순 없을까 하는 의문이 남습니다. 이에 대한 고민도 해보면 좋을 것 같습니다.