
여러 팀들이 문제를 풀어서 제출했을 때, 나의 팀의 순위를 구하는 문제이다.
순위를 구하는 규칙은 아래와 같다.
1. 문제를 제출하면 채점된 점수가 주어지고, 제출하지 않으면 0점으로 간주한다.
2. 최종적인 점수의 총 합으로 순위를 매긴다.
3. 점수의 총 합이 같다면, 답을 제출한 횟수로 순위를 매긴다. (더 적은 쪽이 높은 순위)
4. 답을 제출한 횟수 또한 같다면, 답을 마지막으로 제출한 시간으로 순위를 매긴다.(더 빨리 제출한 쪽이 높은 순위)
풀이 코드
문제에서 주어진 대로 구현하기만 하면 되는 문제이기 때문에, 코드를 보면서 과정을 이해해보자.
먼저, 이 문제는 입력이 많고, 고려해야 할 데이터가 많아서 다소 까다로울 수 있다. 하지만, 구현 자체는 어렵지 않다.
먼저, 본인은 TeamInfo 구조체를 하나 선언하였다.
struct TeamInfo
{
std::vector<int> Scores;
int ID = 0;
int SubmitCount = 0;
int SubmitTime = 0;
int ScoreSum = 0;
};
TeamInfo 구조체에는, 현재 제출된 답의 점수를 저장하는 벡터 Scores가 선언되어 있다.
제출한 답이 기존의 답보다 높은 점수인지 확인하기 위해 해당 벡터를 선언하였다.
ID는 Team의 ID이다. 이 문제는 특정 기준으로 정렬을 해야하는 문제이기 때문에, 정렬 후에도 팀을 구분할 수 있으려면 ID를 따로 저장하고 있어야 한다.
SubmitCount는 답을 제출한 횟수이다.
SubmitTime는 마지막으로 답을 제출한 시간이다.
ScoreSum은 현재 제출한 답들의 점수 총 합이다.
이후, TestCase의 수를 입력받은 뒤, TestCase의 수만큼 반복문을 돌아줄 것이다.
아래는 반복문 내부의 코드이다.
먼저, 입력에 맞게 아래와 같이 입력을 받아주었다.
int NumOfTeam = 0;
int NumOfProb = 0;
int MyTeamID = 0;
int NumOfLog = 0;
std::cin >> NumOfTeam >> NumOfProb >> MyTeamID >> NumOfLog;
팀은 몇 팀이 있는지, 문제는 몇 개가 있는지, 나의 팀의 ID는 무엇인지, Log는 총 몇 개인지를 입력받아 저장하였다.
이후, 아래와 같이 Team의 정보를 담은 배열을 선언하고, 원소들을 초기화해주었다.
std::vector<TeamInfo> Teams(NumOfTeam);
for (int j = 0; j < NumOfTeam; j++)
{
Teams[j].Scores.resize(NumOfProb);
Teams[j].ID = j + 1;
}
다음은, 주어진 로그에 따라 정보를 갱신해주었다.
for (int j = 0; j < NumOfLog; j++)
{
int CurID = 0;
int CurProb = 0;
int CurScore = 0;
std::cin >> CurID >> CurProb >> CurScore;
Teams[CurID - 1].SubmitCount++;
Teams[CurID - 1].SubmitTime = j;
if (CurScore > Teams[CurID - 1].Scores[CurProb - 1])
{
Teams[CurID - 1].ScoreSum -= Teams[CurID - 1].Scores[CurProb - 1];
Teams[CurID - 1].ScoreSum += CurScore;
Teams[CurID - 1].Scores[CurProb - 1] = CurScore;
}
}
먼저, 현재 Log에서 어떤 팀이 어떤 문제에 대한 답을 제출하였고, 몇 점을 받았는지 입력을 받아주었다.
이후, 해당 팀이 답을 제출한 횟수(SubmitCount)를 1만큼 증가시켰고, 마지막으로 답을 제출한 시간(SubmitTime)를 갱신해주었다.
그리고, 현재 제출합 답의 점수가 기존에 제출했던 답의 점수보다 높다면 ScoreSum과 Scores 벡터를 갱신해주었다.
모든 로그에 대해 정보를 갱신했다면, 이제 팀을 순위에 맞게 정렬해주어야 한다.
bool compare(const TeamInfo& _Left, const TeamInfo& _Right)
{
if (_Left.ScoreSum == _Right.ScoreSum)
{
if (_Left.SubmitCount == _Right.SubmitCount)
{
return _Left.SubmitTime < _Right.SubmitTime;
}
return _Left.SubmitCount < _Right.SubmitCount;
}
return _Left.ScoreSum > _Right.ScoreSum;
}
위와 같이, compare 함수를 정의하였다.
두 팀의 점수 총 합이 같다면, 문제를 제출한 횟수를 검사하였고
문제를 제출한 횟수 또한 같다면, 문제를 마지막으로 제출한 시간을 기준으로 bool값을 반환해주었다.
이후, 아래와 같이 sort함수를 이용하여 정렬한 뒤 내 팀의 순위를 탐색하였다.
std::sort(Teams.begin(), Teams.end(), compare);
for (int j = 0; j < NumOfTeam; j++)
{
if (Teams[j].ID == MyTeamID)
{
Answers[i] = j + 1;
break;
}
}
내 팀의 순위를 탐색한 뒤, 순위를 Answer에 저장해주었다.
Testcase에 대한 답을 모두 구한 뒤 마지막으로 Answer에 저장된 값을 모두 출력해주었다.
for (int i = 0; i < Answers.size(); i++)
{
std::cout << Answers[i] << "\n";
}
이렇게 출력하면, 문제 해결 끝이다.
문제에서 하라는 대로 구현하면 어렵지 않게 정답을 구할 수 있다.

코드 전문
#include <iostream>
#include <vector>
#include <algorithm>
void Init()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
struct TeamInfo
{
std::vector<int> Scores;
int ID = 0;
int SubmitCount = 0;
int SubmitTime = 0;
int ScoreSum = 0;
};
bool compare(const TeamInfo& _Left, const TeamInfo& _Right)
{
if (_Left.ScoreSum == _Right.ScoreSum)
{
if (_Left.SubmitCount == _Right.SubmitCount)
{
return _Left.SubmitTime < _Right.SubmitTime;
}
return _Left.SubmitCount < _Right.SubmitCount;
}
return _Left.ScoreSum > _Right.ScoreSum;
}
int main()
{
Init();
int NumOfTestCase = 0;
std::cin >> NumOfTestCase;
std::vector<int> Answers(NumOfTestCase);
for (int i = 0; i < NumOfTestCase; i++)
{
int NumOfTeam = 0;
int NumOfProb = 0;
int MyTeamID = 0;
int NumOfLog = 0;
std::cin >> NumOfTeam >> NumOfProb >> MyTeamID >> NumOfLog;
std::vector<TeamInfo> Teams(NumOfTeam);
for (int j = 0; j < NumOfTeam; j++)
{
Teams[j].Scores.resize(NumOfProb);
Teams[j].ID = j + 1;
}
for (int j = 0; j < NumOfLog; j++)
{
int CurID = 0;
int CurProb = 0;
int CurScore = 0;
std::cin >> CurID >> CurProb >> CurScore;
Teams[CurID - 1].SubmitCount++;
Teams[CurID - 1].SubmitTime = j;
if (CurScore > Teams[CurID - 1].Scores[CurProb - 1])
{
Teams[CurID - 1].ScoreSum -= Teams[CurID - 1].Scores[CurProb - 1];
Teams[CurID - 1].ScoreSum += CurScore;
Teams[CurID - 1].Scores[CurProb - 1] = CurScore;
}
}
std::sort(Teams.begin(), Teams.end(), compare);
for (int j = 0; j < NumOfTeam; j++)
{
if (Teams[j].ID == MyTeamID)
{
Answers[i] = j + 1;
break;
}
}
}
for (int i = 0; i < Answers.size(); i++)
{
std::cout << Answers[i] << "\n";
}
return 0;
}
'코딩테스트 문제 풀이 (C++)' 카테고리의 다른 글
백준 2437 - 저울 (C++) (0) | 2024.04.24 |
---|---|
백준 2668 - 숫자 고르기 (C++) (0) | 2024.04.24 |
백준 2170 - 선 긋기 (C++) (0) | 2024.04.21 |
백준 1987 - 알파벳 (C++) (1) | 2024.04.19 |
백준 1107 - 리모컨 (C++) (0) | 2024.04.19 |