소프티어(Softeer) 성적평가 (C++)

요약

출력의 형태가 각 대회마다의 N번째 사람의 등수를 출력하는 것이므로
N명의 사람들 자체를 정렬하는 방식은 별로다.

---

문제

스터디를 위해 대회를 세 개 개최
참가자는 각 대회에서 0 이상 1,000 이하의 정수인 점수를 얻는다.
한 대회에서 둘 이상의 참가자가 동점이 나오는 경우도 있을 수 있다.


각 대회별 등수 및 최종 등수를 매기고 싶다.
등수는 가장 점수가 높은 사람부터 1등, 2등, ···, N등의 순서대로 붙는다.
만일 동점이 있을 경우 가능한 높은 (등수의 수가 작은) 등수를 부여한다.
각 사람마다 “나보다 점수가 큰 사람”의 수를 세어 1을 더한 것이 자신의 등수가 된다.
대회별 등수는 각 대회에서 얻은 점수를 기준으로 하며 최종 등수는 세 대회의 점수의 합을 기준으로 한다.

각 참가자의 대회별 등수 및 최종 등수를 출력하는 프로그램을 작성하시오.

[제약조건]
3 ≤ N ≤ 100,000

[입력]
첫째 줄에 참가자의 수를 나타내는 정수 N이 주어진다.
이어 세 개의 줄에 각 대회의 결과를 나타내는 N개의 정수가 주어진다.
이중 i번째 정수는 그 대회에서 i번째 사람이 얻은 점수를 의미한다.

[출력]
첫 세 개의 줄에는 각 참가자의 대회별 등수를 출력한다.
이어 새로운 줄에 같은 형식으로 각 참가자의 최종 등수를 출력한다.

---

풀이

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

struct ans{
	int s1, s2, s3, sA;
};
vector<ans>v;
int N;

int maxscore1, maxscore2, maxscore3, maxscoreAll = 0;
vector<int>test1;
vector<int>test2;
vector<int>test3;
vector<int>testAll;

int score1[1001] = { 0, };
int score2[1001] = { 0, };
int score3[1001] = { 0, };
int scoreAll[3001] = { 0, };

int prefix1[1001] = { 0, };
int prefix2[1001] = { 0, };
int prefix3[1001] = { 0, };
int prefixAll[3001] = { 0, };


void init() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		score1[a]++;
		test1.push_back(a);
		if (a > maxscore1) maxscore1 = a;
	}
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		score2[a]++;
		test2.push_back(a);
		if (a > maxscore2) maxscore2 = a;
	}
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		score3[a]++;
		test3.push_back(a);
		if (a > maxscore3) maxscore3 = a;
	}
}

void make_test3() {
	for (int i = 0; i < N; i++) {
		int a = test1[i] + test2[i] + test3[i];
		scoreAll[a]++;
		testAll.push_back(a);
		if (a > maxscoreAll) maxscoreAll = a;
	}
}

// prefix = idx 점수보다 점수가 높은 사람의 수
void calc() {

	prefix1[maxscore1] = 0;
	prefix2[maxscore2] = 0;
	prefix3[maxscore3] = 0;
	prefixAll[maxscoreAll] = 0;

	for (int i = maxscore1 - 1; i >= 0; i--) {
		prefix1[i] = prefix1[i + 1] + score1[i + 1];
	}
	for (int i = maxscore2 - 1; i >= 0; i--) {
		prefix2[i] = prefix2[i + 1] + score2[i + 1];
	}
	for (int i = maxscore3 - 1; i >= 0; i--) {
		prefix3[i] = prefix3[i + 1] + score3[i + 1];
	}
	for (int i = maxscoreAll - 1; i >= 0; i--) {
		prefixAll[i] = prefixAll[i + 1] + scoreAll[i + 1];
	}
}

void calc2() {
	for (int i = 0; i < N; i++) {
		int s1 = prefix1[test1[i]] + 1;
		int s2 = prefix2[test2[i]] + 1;
		int s3 = prefix3[test3[i]] + 1;
		int sA = prefixAll[testAll[i]] + 1;
		v.push_back({ s1,s2,s3,sA });
	}
}

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

	init();
	make_test3();
	calc();
	calc2();

	for (int i = 0; i < N; i++) {
		cout << v[i].s1 << " ";
	}
	cout << "\n";
	for (int i = 0; i < N; i++) {
		cout << v[i].s2 << " ";
	}
	cout << "\n";
	for (int i = 0; i < N; i++) {
		cout << v[i].s3 << " ";
	}
	cout << "\n";
	for (int i = 0; i < N; i++) {
		cout << v[i].sA << " ";
	}

	return 0;
}