[프로그래머스 Lv3] : 순위

문제 링크

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

코딩테스트 연습 - 순위

경기 결과의 전체가 아닌 일부가 주어졌을 때, 순위를 정확히 알 수 있는 선수의 수를 리턴하는 문제.

 

풀이

만약 경기 전체의 결과가 주어졌다면 모순이 없다는 전제 하에 위상정렬로 풀 수 있다.

하지만 경지 전체의 결과가 아닌 일부만 주어졌기 때문에 위상정렬을 사용할 수가 없었다.

 

• 풀이 알고리즘

순위를 정확히 알 수 있는 선수는 어떤 선수들인가?

자신을 제외한 n-1명과의 경기 결과가 모두 드러난 선수는 순위를 알 수 있다.

하지만 주어진 경기결과엔 제한이 있기때문에 주어진 결과를 이용해서 경기결과를 예측해야한다.

결과는 100% 실력에 의해서 결정되므로 결과가 바뀌는 경우는 없다.

선수 A와 B가 있다고 하자.

이때 선수 A가 B를 이겼다는 결과가 주어졌다. 그럼 이 결과에 대해서 우리는 2가지 정보를 추가로 얻을 수 있다.

1. B가 이기는 선수는 A도 이긴다.

2. A가 못이기는 선수는 B도 못이긴다.

 

이 과정을 통해서 우리는 경기 결과를 채워나간다.

마지막까지 본인을 제외한 n-1명과의 결과를 알지못하는 선수는 순위를 알 수 없는 선수다.

 

• 필요한 자료들

1. 임의의 선수 i 에 대해 i가 이길 수 있는 선수들의 명단 & i가 못이기는 선수들의 명단

이 명단은 초기에 주어진 결과들로 채울 수 있고, 이후 추론한 정보로도 채울 수 있다.

i가 이길 수 있는 선수들의 수 + 못이기는 선수들의 수 가 n-1이 될 때 선수 i 의 순위를 알 수 있다.

이때 선수들의 명단은 중복이 되면 안되므로 set을 이용해서 중복을 알아서 방지하게끔 했다.

set<int> Can_Win[ i ] 에는 i 선수가 이길 수 있는 선수들의 명단을

set<int> Cant_Win[ i ] 에는 i 선수가 이기지 못하는 선수들의 명단을 저장했다.

 

 2. 선수 i가 선수 j를 이기는 지 여부

두 선수가 주어졌을 때 누가 이기는 지를 매번 주어진 벡터를 탐색하면서 찾는다면 시간이 너무 오래걸린다.

Result라는 2차원 배열을 만들어서 Result[ i ][ j ] == true면 i가 j를 이기는 것이라고 판단.

반대로 Result[ j ][ i ] == true면 j가 i를 이긴다고 판단.

 

3. 이미 순위가 확정된 선수 인지 체크

visited 배열을 만들어서 선수 i 가 이미 순위가 확정된 선수인지 체크했다.

만약 이미 확정된 선수라면 굳이 i에 대해 조사할 필요가 없다.

 

코드 작성

#include <string>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int MAX_N = 100 + 5;
bool Result[MAX_N][MAX_N];
bool visited[MAX_N];
set<int> Can_Win[MAX_N];
set<int> Cant_Win[MAX_N];
vector<int> Edge[MAX_N];
 
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for(int i = 0; i<results.size(); i++){
        int winner = results[i][0];
        int loser = results[i][1];
        Edge[winner].push_back(loser);
        Edge[loser].push_back(winner);
        Result[winner][loser] = true;
        Can_Win[winner].insert(loser);
        Cant_Win[loser].insert(winner);
    }
    
    for(int i = 1; i<=n; i++){
        for(int j = 0; j<Edge[i].size(); j++){
            int rival = Edge[i][j];
            if(Result[i][rival]){
                //i가 rival을 이김
                // i가 이길 수 없는 상대는 rival도 못이김
                // rival이 이기는 상대는 i도 이김
                for(auto it : Cant_Win[i])
                    Cant_Win[rival].insert(it);
                for(auto it : Can_Win[rival])
                    Can_Win[i].insert(it);
            }
            else if(Result[rival][i]){
                //rival이 이김
                //rival이 이길 수 없는 상대는 i도 못이김
                // i가 이기닌 상대는 rival도 이김
                for(auto it : Can_Win[i])
                    Can_Win[rival].insert(it);
                for(auto it : Cant_Win[rival])
                    Cant_Win[i].insert(it);
            }
        }
    }
    queue<int> q;
    for(int i = 1; i<=n; i++){
        if(Can_Win[i].size() + Cant_Win[i].size() == n - 1) //순위가 결정된 선수
            q.push(i);
    }
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        if(visited[now]) //이미 결정난 선수면 패스
            continue;
        answer++;
        visited[now] = true;
        for(int i = 0; i<Edge[now].size(); i++){
            int rival = Edge[now][i];
            if(Result[now][rival]){ //내가 이김
                //나를 이기는 사람은 상대도 이김
                for(auto it : Cant_Win[now])
                    Cant_Win[rival].insert(it);
            }
            else if(Result[rival][now]){ //상대가 이김
                //내가 이긴사람은 상대도 이김
                for(auto it : Can_Win[now])
                   Can_Win[rival].insert(it);
            }
            if(Can_Win[rival].size() + Cant_Win[rival].size() == n-1 && !visited[rival])
                q.push(rival);
        }
    }
    return answer;
}