[프로그래머스/C++] 순위

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 순위가 확실한 인원들의 수를 return 하면 되는 문제다.

 

문제는 순위가 확실한지 파악하는 방법인데, 이는 반복을 통해 쉽게 파악 할 수 있다.

 

A가 B를 이기면 A를 이긴 사람들은 전부 B를 이긴다.

반대로 A에게 B가 졌다면 B에게 진 사람들을 전부 A에게 진다.

 

그러므로 A에게 이긴 선수가 있다면, A에게 진 선수들에게도 이긴 선수의 수를 1 더해주면 된다.

반대로 A에게 진 선수가 있다면, A에게 이긴 선수들에게도 진 선수의 수를 1 더해주면 된다.

 

이렇게 계산하면 단순히 특정선수를 이긴 사람의 수와 진 사람의 수를 파악하는 것 만으로도 쉽게 문제를 풀 수 있다.

 

+ 위 제한사항에 보면 선수의 수가 많지 않기 때문에 조건들을 잘 활용해 반복문으로 구현하면 쉽게 구할 수 있다.

 

 

[아이디어 정리]

1. A선수를 이긴 선수는 A선수가 이긴 선수들을 모두 이길 수 있다.
2. B선수에게 진 선수는 B선수가 진 선수들에게서 전부 진다.
3. 내가 이긴 선수의 수와 진 선수의 수의 합이 전체 선수의 합+1 과 같다면 순위를 확실하게 안다. (A선수는 A한테 이기고 진다는 조건 둘 다 포함 시켰기 때문에 +1과 같아야 한다.)

 

Code

 

 

 

#include <string>
#include <vector>

using namespace std;
vector<vector<bool>> winRank;
vector<vector<bool>> loseRank;
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    winRank=vector<vector<bool>>(n+1,vector<bool>(n+1,false)); //나를 이긴 사람
    loseRank=vector<vector<bool>>(n+1,vector<bool>(n+1,false)); //나한테 진 사람
    for (int i=0; i<n+1; i++)
    {
        winRank[i][i]=true;
        loseRank[i][i]=true;
    }
    for (int i=0; i<results.size(); i++)
    {
        for (int j=1; j<winRank[results[i][0]].size(); j++)
        {
            // results[i][0]를 이긴 사람은 results[i][0] 에 진사람한테도 이긴다.
            if (winRank[results[i][0]][j]) 
            {
                winRank[results[i][1]][j]=true;
                for (int k=1; k<n+1; k++)
                {
                    if (loseRank[results[i][1]][k])
                    {
                        winRank[k][j]=true;
                    }
                }
            }
            if (loseRank[results[i][1]][j])
            {
                loseRank[results[i][0]][j]=true;
                for (int k=1; k<n+1; k++)
                {
                    if (winRank[results[i][0]][k])
                    {
                        loseRank[k][j]=true;
                    }
                }
            }
        }
    }
    for (int i=0; i<n+1; i++)
    {
        int cnt=0;
        for (int j=0; j<n+1; j++)
        {
            if (loseRank[i][j])
            {
                cnt+=1;
            }
            if (winRank[i][j])
            {
                cnt+=1;
            }
        }
        if (cnt==n+1)
        {
            answer+=1;
        }
    }
    return answer;
}

 

 

---

 

for문을 사용하면 쉽게 풀 수 있는 문제였다. 만약 set을 썼다면 조금 더 빨랐을 것 같지만, 수가 크지 않아서 vector를 사용해 빠르게 해결했다.

 

프로그래머스