[백준 3758] - KCPC(C++)

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

구현이 중요한 문제입니다.

문제 분석

크게 문제에서 구현해야 할 부분은

1. 점수를 입력받은 후 팀 아이디, 문제 별로 가장 높은 점수를 저장
2. 팀 별로 총점 구하기
3. 팀별 순위 매기기 (동점인 경우 제출횟수가 적은 순, 제출 시간이 빠른순으로)
4. 입력받은 팀 아이디(=t) 의 순위를 출력하기

 

 로 나뉘어진다.

map을 활용하여 1, 2를 해결했고

3을 위해서 구조체를 따로 정의했다.

struct finalscore
{
    int team;
    int score;
    int submit; // 제출 횟수
    int lastsubmit; // 마지막 제출 순번
};

compare() 함수를 활용하면 사용자가 정의한 기준으로 정렬할 수 있다.

동점일 시 제출횟수가 적은 것 우선,

제출횟수 및 점수가 동일할 시 마지막 제출 순번이 빠른 것을 우선하도록 구현했다.

bool compare(finalscore tp1, finalscore tp2)
{
    if (tp1.score!= tp2.score)
    {
        return tp1.score > tp2.score;
    }
    else
    {
        if (tp1.submit!= tp2.submit)
        {
            return tp1.submit < tp2.submit;
        }
        return tp1.lastsubmit < tp2.lastsubmit;
    }
}

소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <map>
using namespace std;

struct finalscore
{
    int team;
    int score;
    int submit;
    int lastsubmit;
};

bool compare(finalscore tp1, finalscore tp2)
{
    if (tp1.score!= tp2.score)
    {
        return tp1.score > tp2.score;
    }
    else
    {
        if (tp1.submit!= tp2.submit)
        {
            return tp1.submit < tp2.submit;
        }
        return tp1.lastsubmit < tp2.lastsubmit;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        int n, k, t, m;
        cin >> n >> k >> t >> m;
        map<int, map<int, int>> list;
        // 팀 아이디, 제출 횟수
        // 팀 아이디, 마지막 제출
        map<int, int> submitcnt;
        map<int, int> lastcnt;
        int cnt = 1;
        for (int j = 0; j < m; j++)
        {
            // 팀 아이디, 문제 번호, 점수
            int tid, pn, score;
            cin >> tid >> pn >> score;
            if (list[tid][pn] < score)
            {
                list[tid][pn] = score;
            }
            submitcnt[tid]++;
            lastcnt[tid] = cnt;
            cnt++;
        }
        // 팀별 점수
        vector<finalscore> sumscore;
        for (auto& team : list)
        {
            int tid = team.first;
            int tmp = 0;

            for (auto& prob : team.second)
            {
                tmp += prob.second;
            }

            sumscore.push_back({ tid, tmp, 0, 0 });
        }

        for (auto &s:submitcnt)
        {
            for (auto &a:sumscore)
            {
                if (s.first == a.team)
                {
                    a.submit = s.second;
                }
            }
        }

        for (auto& l : lastcnt)
        {
            for (auto& a : sumscore)
            {
                if (l.first == a.team)
                {
                    a.lastsubmit = l.second;
                }
            }
        }

        sort(sumscore.begin(), sumscore.end(), compare);
        int count = 1;
        for (int i = 0; i < sumscore.size(); i++)
        {
            if (sumscore[i].team == t)
            {
                cout << count << "\n";
            }
            else
            {
                count++;
            }
        }
    }
}