Featured image of post [Algorithm] C++/Python 백준 5544번 : 리그 순위 계산
Algorithm Implementation Sorting

[Algorithm] C++/Python 백준 5544번 : 리그 순위 계산

리그에서 각 팀의 승점과 순위를 정확히 계산하는 것은 스포츠 통계에서 매우 중요한 작업이다. 이번 포스트에서는 백준의 문제 5544번 “리그 순위 계산"을 통해 팀들의 승점을 기반으로 순위를 결정하는 방법을 살펴본다. 이 문제는 주어진 경기 결과를 바탕으로 각 팀의 승점을 계산하고, 이를 바탕으로 팀들의 순위를 매기는 과정을 구현하는 것이 목표이다.

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

문제 설명

축구 리그에 총 N개의 팀이 소속되어 있으며, 각 팀은 1부터 N까지 번호가 매겨져 있다. 리그에서는 모든 팀 간의 경기가 한 번씩 열리며, 총 N(N-1)/2 경기가 진행된다. 각 경기에서 많은 득점을 한 팀이 승리하게 되며, 승리한 팀은 3점을 획득하고, 패배한 팀은 0점을 획득한다. 만약 두 팀이 득점이 동일할 경우, 두 팀 모두 1점씩을 획득한다.

리그의 순위는 각 팀이 획득한 총 승점의 합으로 결정되며, 동일한 승점을 가진 팀들은 가능한 가장 높은 순위를 공유한다. 예를 들어, 총 4개의 팀이 리그에 참여하여 각 경기의 결과가 주어진 경우, 각 팀의 승점을 계산하고 이를 기반으로 순위를 결정하게 된다. 이때, 승점이 동일한 팀은 동일한 순위를 가지며, 그 다음 순위는 승점이 높은 팀들의 수에 따라 조정된다.

주어진 N과 각 경기의 결과가 주어질 때, 각 팀의 순위를 계산하여 출력하는 프로그램을 작성해야 한다.

접근 방식

이 문제는 기본적인 구현 문제로, 주어진 경기 결과를 바탕으로 각 팀의 승점을 계산한 후, 이를 통해 팀들의 순위를 결정하는 과정을 구현하면 된다. 구체적인 접근 방식은 다음과 같다:

  1. 입력 처리: 팀의 수 N과 N(N-1)/2개의 경기 결과를 입력받는다. 각 경기 결과는 팀 A와 팀 B의 득점 C, D로 주어진다.

  2. 승점 계산: 각 경기 결과를 바탕으로 팀 A와 팀 B의 승점을 업데이트한다.

    • 팀 A의 득점 C가 팀 B의 득점 D보다 크면 팀 A는 3점을 획득한다.
    • 팀 B의 득점 D가 팀 A의 득점 C보다 크면 팀 B는 3점을 획득한다.
    • 득점이 동일하면 두 팀 모두 1점씩을 획득한다.

  3. 순위 결정: 각 팀의 총 승점을 기반으로 순위를 결정한다.

    • 각 팀의 승점이 더 높은 팀의 수를 계산하여 순위를 매긴다.
    • 동일한 승점을 가진 팀들은 동일한 순위를 가지며, 가능한 가장 높은 순위를 할당한다.

  4. 출력: 각 팀의 순위를 순서대로 출력한다.

이 과정에서 중요한 점은 승점이 동일한 팀들은 동일한 순위를 가지며, 그 다음 순위는 이전에 높은 순위를 차지한 팀들의 수에 따라 결정된다는 점이다. 이를 구현하기 위해 각 팀의 승점을 비교하여 순위를 매기는 과정을 반복하면 된다.

C++ 코드와 설명

아래는 문제를 해결하기 위한 최적화된 C++ 코드이다. 코드에는 라인별 주석을 추가하여 각 부분의 역할을 설명하였다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    // 팀의 점수를 저장하는 벡터 초기화 (1번부터 N번까지)
    vector<int> points(N+1, 0);
    
    // 총 경기 수는 N*(N-1)/2
    int total_matches = N*(N-1)/2;
    
    for(int i=0; i<total_matches; ++i){
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        
        if(C > D){
            points[A] += 3; // 팀 A가 승리하여 3점 획득
        }
        else if(C < D){
            points[B] += 3; // 팀 B가 승리하여 3점 획득
        }
        else{
            points[A] +=1;  // 무승부로 팀 A에 1점 추가
            points[B] +=1;  // 무승부로 팀 B에 1점 추가
        }
    }
    
    // 각 팀의 순위를 계산하여 출력
    for(int i=1; i<=N; ++i){
        int rank = 1;
        for(int j=1; j<=N; ++j){
            if(points[j] > points[i]){
                rank++; // 팀 i보다 승점이 높은 팀의 수만큼 순위 증가
            }
        }
        cout << rank << "\n"; // 팀 i의 순위 출력
    }
    
    return 0;
}

코드 설명

  1. 입력 및 초기화:

    • N을 입력받아 팀의 수를 결정한다.
    • points 벡터를 크기 N+1로 초기화하여 각 팀의 점수를 저장한다. 팀 번호는 1부터 시작하므로 인덱스 0은 사용하지 않는다.

  2. 경기 결과 처리:

    • 총 경기 수는 N*(N-1)/2이므로, 이만큼 반복하여 각 경기의 결과를 입력받는다.
    • 각 경기의 결과 A B C D를 입력받아, 팀 A와 팀 B의 득점 C와 D를 비교한다.
      • 팀 A가 승리하면 팀 A에게 3점을 추가한다.
      • 팀 B가 승리하면 팀 B에게 3점을 추가한다.
      • 무승부인 경우, 두 팀 모두에게 1점씩을 추가한다.

  3. 순위 계산:

    • 각 팀에 대해 순위를 계산한다.
    • 팀 i의 순위는 팀 i보다 승점이 높은 팀의 수에 1을 더한 값이다.
    • 동일한 승점을 가진 팀은 동일한 순위를 가지므로, 가능한 가장 높은 순위를 할당한다.

  4. 출력:

    • 각 팀의 순위를 순서대로 출력한다.

예제 실행

예제 입력 1

1
2
3
4
5
6
7

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

1
2
3
4

2
1
4
2

이 예제에서는 팀 2가 가장 높은 승점을 획득하여 1위를 차지하며, 팀 1과 팀 4는 동일한 승점을 가지므로 2위를 공유하고, 팀 3은 4위를 차지하게 된다.

C++ without library 코드와 설명

아래는 C++에서 표준 라이브러리를 사용하지 않고, stdio.h와 malloc.h만을 사용하여 최적화된 코드를 작성한 예제이다. 이 코드는 같은 기능을 수행하며, 각 부분에 주석을 추가하여 설명하였다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <stdio.h>
#include <stdlib.h>

int main(){
    int N;
    scanf("%d", &N);
    
    // 팀의 점수를 저장할 배열 동적 할당 (1번부터 N번까지)
    int* points = (int*)calloc(N+1, sizeof(int));
    
    int total_matches = N*(N-1)/2;
    for(int i=0; i<total_matches; ++i){
        int A, B, C, D;
        scanf("%d %d %d %d", &A, &B, &C, &D);
        
        if(C > D){
            points[A] += 3; // 팀 A 승리
        }
        else if(C < D){
            points[B] += 3; // 팀 B 승리
        }
        else{
            points[A] +=1; // 무승부
            points[B] +=1;
        }
    }
    
    // 각 팀의 순위를 계산하여 출력
    for(int i=1; i<=N; ++i){
        int rank = 1;
        for(int j=1; j<=N; ++j){
            if(points[j] > points[i]){
                rank++;
            }
        }
        printf("%d\n", rank); // 팀 i의 순위 출력
    }
    
    free(points); // 동적 할당 메모리 해제
    return 0;
}

코드 설명

  1. 입력 및 초기화:

    • scanf를 사용하여 팀의 수 N을 입력받는다.
    • calloc을 사용하여 팀의 점수를 저장할 배열 points를 동적으로 할당한다. 모든 요소는 초기값 0으로 설정된다.

  2. 경기 결과 처리:

    • 총 경기 수 N*(N-1)/2만큼 반복하여 각 경기의 결과를 scanf로 입력받는다.
    • 팀 A와 팀 B의 득점 C와 D를 비교하여 승점을 업데이트한다.
      • 팀 A가 승리하면 팀 A에게 3점을 추가한다.
      • 팀 B가 승리하면 팀 B에게 3점을 추가한다.
      • 무승부인 경우, 두 팀 모두에게 1점씩을 추가한다.

  3. 순위 계산:

    • 각 팀에 대해 순위를 계산한다.
    • 팀 i의 순위는 팀 i보다 승점이 높은 팀의 수에 1을 더한 값이다.

  4. 출력:

    • printf를 사용하여 각 팀의 순위를 순서대로 출력한다.

  5. 메모리 관리:

    • free를 사용하여 동적으로 할당된 points 배열의 메모리를 해제한다.

예제 실행

예제 입력 1

1
2
3
4
5
6
7

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

1
2
3
4

2
1
4
2

이 예제에서도 동일하게 팀 2가 1위를, 팀 1과 팀 4가 2위를, 팀 3이 4위를 차지한다.

Python 코드와 설명

아래는 문제를 해결하기 위한 최적화된 Python 코드이다. 코드에는 주석을 추가하여 각 부분의 역할을 설명하였다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx +=1
    
    points = [0]*(N+1)  # 팀의 점수를 저장할 리스트 초기화
    
    total_matches = N*(N-1)//2
    for _ in range(total_matches):
        A = int(data[idx])
        B = int(data[idx+1])
        C = int(data[idx+2])
        D = int(data[idx+3])
        idx +=4
        
        if C > D:
            points[A] +=3  # 팀 A 승리
        elif C < D:
            points[B] +=3  # 팀 B 승리
        else:
            points[A] +=1  # 무승부
            points[B] +=1
    
    for i in range(1, N+1):
        rank = 1
        for j in range(1, N+1):
            if points[j] > points[i]:
                rank +=1
        print(rank)

if __name__ == "__main__":
    main()

코드 설명

  1. 입력 및 초기화:

    • sys.stdin.read를 사용하여 모든 입력을 한 번에 읽어들인다.
    • 입력된 데이터를 공백 기준으로 분리하여 리스트 data에 저장한다.
    • 팀의 수 N을 data 리스트에서 읽어온다.
    • points 리스트를 크기 N+1로 초기화하여 각 팀의 점수를 저장한다. 인덱스 0은 사용하지 않는다.

  2. 경기 결과 처리:

    • 총 경기 수 N*(N-1)//2만큼 반복하여 각 경기의 결과를 처리한다.
    • 각 경기의 결과 A, B, C, D를 data 리스트에서 읽어온다.
    • 팀 A와 팀 B의 득점 C와 D를 비교하여 승점을 업데이트한다.
      • 팀 A가 승리하면 팀 A에게 3점을 추가한다.
      • 팀 B가 승리하면 팀 B에게 3점을 추가한다.
      • 무승부인 경우, 두 팀 모두에게 1점씩을 추가한다.

  3. 순위 계산:

    • 각 팀에 대해 순위를 계산한다.
    • 팀 i의 순위는 팀 i보다 승점이 높은 팀의 수에 1을 더한 값이다.

  4. 출력:

    • 각 팀의 순위를 순서대로 출력한다.

예제 실행

예제 입력 1

1
2
3
4
5
6
7

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

1
2
3
4

2
1
4
2

이 예제에서도 동일하게 팀 2가 1위를, 팀 1과 팀 4가 2위를, 팀 3이 4위를 차지한다.

결론

이번 포스트에서는 백준의 문제 5544번 “리그 순위 계산"을 통해 각 팀의 승점을 계산하고 이를 기반으로 순위를 결정하는 방법을 구현하였다. 이 문제는 기본적인 구현 문제로, 경기 결과를 정확히 처리하고 승점을 올바르게 계산하는 것이 핵심이었다. C++과 Python 두 가지 언어로 문제를 해결하면서 각 언어의 특성에 맞는 최적화 방법을 적용해 보았다.

특히, 팀의 승점을 효율적으로 계산하고 순위를 결정하기 위해 반복문을 활용한 간단한 방법을 사용하였다. 문제의 규모가 크지 않기 때문에 이와 같은 방법으로도 충분히 빠른 시간 내에 해결할 수 있었다. 추가적으로, 팀의 순위를 계산할 때 동일한 승점을 가진 팀들이 동일한 순위를 가지도록 처리하는 것이 중요하였다. 이를 통해 문제에서 요구하는 순위 계산 방식을 정확히 구현할 수 있었다.

앞으로 유사한 문제를 해결할 때, 입력 처리와 승점 계산을 효율적으로 구현하는 방법을 적용할 수 있을 것이며, 다양한 문제 유형에 맞는 구현 전략을 개발하는 데 도움이 될 것이다.