[BOJ] C++ 3758: KCPC - 정렬 기준 설정하기

3758번: KCPC

예제

2
3 4 3 5
1 1 30
2 3 30
1 2 40
1 2 20
3 1 70
4 4 1 10
1 1 50
2 1 20
1 1 80
3 1 0
1 2 20
2 2 10
4 3 0
2 1 0
2 2 100
1 4 20

ans : 
1
2

---

정렬 기준이 3가지에 팀 번호까지 저장해둬야 한다. 정렬 기준은 다음과 같다.

1. 최종 점수가 높을수록 등수가 낮다.
2. 제출한 횟수가 낮을수록 등수가 낮다.
3. 마지막 제출 시간이 낮을수록 등수가 낮다.

그리고 로그의 수 m이 최대 10000이므로 O(m log m)으로 풀어야 한다. 그럼 맵이나 정렬을 생각해 두고 구현에 들어갔다.

 

최종 점수를 계산하려면 과목별 점수를 계산해야 한다. 팀 코드와 문제 번호가 1~n, k까지 꽉 채워져있는지 랜덤으로 정해지는지 모르겠지만 일단 꽉 채워져 있다고 가정하고 풀었다. 각 팀의 과목별 점수와 제출한 횟수, 마지막 제출 시간을 먼저 다 따로 기록했다. 

int score[101][101] = {}; // score[팀id][문제id] = 점수
int cnt[101] = {};        // 팀별 제출 회수
int idx[101] = {};        // 팀별 마지막 제출 시간
int n, k, t, m;
cin >> n >> k >> t >> m;
t--;

for (int i = 0; i < m; i++)
{
    int tid, pid, score_;
    cin >> tid >> pid >> score_;
    tid--;
    pid--;

    score[tid][pid] = max(score[tid][pid], score_);
    cnt[tid]++;
    idx[tid] = i;
}

이제 이걸 정렬해주면 된다. 우선 아래 게시글을 참고해 보자!

[C++] 맵과 우선 순위 큐에서 정렬 기준 재정의하기

이 게시글에서 필요한 내용만 한 줄 요약하자면 pair의 기본 정렬을 - 부호를 이용해서 사용하면 코드가 간단하다!

정렬 우선순위대로 벡터에 넣고 기본 sort를 쓰되, 내림차순으로 정렬할 데이터는 -를 붙이는 식으로 정렬했다.

vector<pair<pair<int, int>, pair<int, int>>> result;
// first = {최종 점수, cnt}, second = {마지막 제출 시간, tid}

for (int tid = 0; tid < n; tid++)
{
    int sum = 0;
    for (int j = 0; j < k; j++)
        sum += score[tid][j];
    result.push_back({{sum, -cnt[tid]}, {-idx[tid], tid}});
}

sort(result.begin(), result.end());

이렇게 하면 result 벡터는 최종 순위의 역순으로 정렬되어 있다! 

/** 정렬 3758 KCPC **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int score[101][101] = {}; // score[팀id][문제id] = 점수
        int cnt[101] = {};        // 팀별 제출 회수
        int idx[101] = {};        // 팀별 마지막 제출 시간
        int n, k, t, m;
        cin >> n >> k >> t >> m;
        t--;

        for (int i = 0; i < m; i++)
        {
            int tid, pid, score_;
            cin >> tid >> pid >> score_;
            tid--;
            pid--;

            score[tid][pid] = max(score[tid][pid], score_);
            cnt[tid]++;
            idx[tid] = i;
        }

        vector<pair<pair<int, int>, pair<int, int>>> result;
        // first = {최종 점수, cnt}, second = {마지막 제출 시간, tid}
        
        for (int tid = 0; tid < n; tid++)
        {
            int sum = 0;
            for (int j = 0; j < k; j++)
                sum += score[tid][j];
            result.push_back({{sum, -cnt[tid]}, {-idx[tid], tid}});
        }

        sort(result.begin(), result.end());

        for (int i = 0; i < n; i++)
            if (result[i].second.second == t)
                cout << n - i << '\n';
    }
}