[C++][백준] [정렬] 5544 리그

https://www.acmicpc.net/problem/5544

5544번: 리그

문제

축구 리그에 총 N개의 팀이 소속되어 있고, 1부터 N까지 번호가 매겨져 있다. 이 리그는 모든 조합의 경기가 한 번씩 열린다. 즉, N(N-1)/2 경기가 열리게 된다. 각 경기에서 많은 득점을 한 팀이 이기게 된다. 이긴 팀은 승점 3점을 가져가고, 지는 팀은 0점을 가져간다. 무승부의 경우에는 두 팀이 각각 1점씩 가져가게 된다. 리그 순위는 각 팀이 획득한 승점의 합계로 결정하고, 득실차는 생각하지 않는다. 승점의 합이 동일한 팀의 순위는 가능한 순위 중 가장 높은 것이다.

예를 들어, 4 팀이 리그에 참가한다고 하자. 그럼, 총 4(4-1)/2 = 6경기가 열린다. 결과는 다음과 같다고 하자. 하이픈의 왼쪽 점수는 왼쪽에 있는 팀의 점수이고, 오른쪽 점수는 위쪽에 있는 팀의 점수이다.

 팀 1팀 2팀 3팀 4승무패승점팀 1팀 2팀 3팀 4

---	0 - 1	2 - 1	2 - 2	1	1	1	4
1 - 0	---	1 - 1	3 - 0	2	1	0	7
1 - 2	1 - 1	---	1 - 3	0	1	2	1
2 - 2	0 - 3	3 - 1	---	1	1	1	4

승점이 가장 높은 팀 2가 1위가 된다. 그 다음으로 승점이 높은 팀은 팀 1과 팀 4이며, 두 팀의 순위는 2위이다. 마지막으로 승점이 가장 낮은 팀 3은 4위가 된다.

모든 경기의 결과가 주어졌을 때, 각 팀의 순위를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 팀의 수 N (2 ≤ N ≤ 100)가 주어진다. 다음 N(N-1)/2개 줄에는 각 경기의 결과가 주어진다. 경기의 결과는 A B C D와 같이 네 개의 정수로 나타내며, A팀이 C점, B팀이 D점을 획득했음을 의미한다. A와 B는 항상 다르다. 한 경기의 결과가 여러 번 주어지는 경우는 없다.

출력

출력은 총 N줄을 출력한다. i번째 줄에는 팀 i의 순위를 출력한다.

예제 입력 1

4

1 2 0 1

1 3 2 1

1 4 2 2

2 3 1 1

2 4 3 0

3 4 1 3

예제 출력 1

2

1

4

2

 

풀이

처음에 삽입정렬을 이용했는데 틀렸습니다. 라고 떠서 sort()를 이용했다.

Team 클래스를 만들어 인덱스와 스코어를 관리해주었다.

그리고 조건에 맞게 a의 점수인 c가 b의 점수인 d보다 크면 a는 3점을 얻고 반대면 b가 3점을 얻는다. 

동점이면 각각 1점씩 얻는다. 

팀을 인덱스 1234로 관리했기 때문에  sort(soccer + 1, soccer + n + 1, compare); 1을 더해서 정렬시켜 주었다.

그리고 얻은 점수에 따라 순위를 부여했다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
class Team {
public:
    int index;
    int score = 0;
};
 
bool compare(Team a, Team b) {
    return a.score < b.score;
}
 
int main() {
    int n; cin >> n;
    Team soccer[101];
    int rank[101];
 
    for (int i = 1; i <= n; i++)
        soccer[i].index = i;
 
    int m = (n*(n - 1)) / 2;
    
    for (int i = 0; i < m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        if (c > d)
            soccer[a].score += 3;
        else if (c < d)
            soccer[b].score += 3;
        else {
            soccer[a].score++;
            soccer[b].score++;
        }
    }
    sort(soccer + 1, soccer + n + 1, compare);
 
    int grade = 1;
    rank[soccer[n].index] = 1;
    for (int i = n - 1; i >= 1; i--) {
        if (soccer[i].score < soccer[i + 1].score)
            rank[soccer[i].index] = ++grade;
        else {
            rank[soccer[i].index] = rank[soccer[i + 1].index];
            grade++;
        }
    }
 
    for (int i = 1; i <= n; i++)
        cout << rank[i] << '\n';
}