문제
N개 팀이 참가하는 축구 리그에서 각 경기 결과가 주어진다. 승리 시 3점, 무승부 시 1점씩, 패배 시 0점을 부여한다. 모든 경기 결과를 처리한 후 각 팀의 최종 순위를 출력한다.
동점인 팀은 같은 순위를 갖는다. 순위는 점수가 높을수록 낮은 숫자(상위 순위)를 갖는다.
입력
- 첫 번째 줄: 팀 수 N
- 이후 여러 줄: 경기 결과
A B C D(A팀 vs B팀, A팀 C골 B팀 D골) - EOF로 종료
출력
- 팀 번호 1번부터 N번까지 각 팀의 순위를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 2 3 1 2 3 0 0 1 3 2 2 | 1 2 3 |
풀이
각 경기 결과에 따라 점수를 누적하고, 정렬 후 동점 처리를 포함한 순위를 계산한다.
- N개 팀의 점수 배열을 0으로 초기화한다.
- EOF까지 경기 결과
A B C D를 입력받는다. - C
>D이면 A팀에 3점, C<D이면 B팀에 3점, 동점이면 양팀에 1점씩 부여한다. - 점수와 원래 팀 번호를 쌍으로 저장하고 점수 오름차순으로 정렬한다.
- 역순으로 순위를 계산한다. 이전 팀과 점수가 다르면 현재 순위를
N - i로 갱신하고, 같으면 이전 순위를 유지한다. - 팀 번호 순서대로 순위를 출력한다.
핵심 아이디어: (점수, 팀번호) 쌍을 정렬하면 동점 처리가 쉬워진다. 오름차순 정렬 후 역순으로 순위를 매기되, 점수가 동일한 구간은 같은 순위를 부여한다. 순위 배열 ans[]를 팀 번호로 인덱싱하여 최종 출력한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int, int> arr[100];
int ans[101];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i < N; i++)
arr[i].second = i + 1;
int A, B, C, D;
while (cin >> A >> B >> C >> D)
{
A--;
B--;
if (C < D)
arr[B].first += 3;
else if (C > D)
arr[A].first += 3;
else
arr[A].first++, arr[B].first++;
}
sort(arr, arr + N);
ans[arr[N - 1].second] = 1;
int r = 1;
for (int i = N - 2; i > -1; i--)
{
if (arr[i].first != arr[i + 1].first)
r = N - i;
ans[arr[i].second] = r;
}
for (int i = 1; i <= N; i++)
cout << ans[i] << '\n';
}복잡도
- 시간: O(M + N log N) — M개의 경기 처리 후 N팀 정렬
- 공간: O(N) — 팀 정보 및 순위 배열