[소프티어] 성적 평가 / C++ 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=1309 

Softeer

#include <iostream>

using namespace std;
int main(int argc, char** argv)
{
	int n;
	int cnt[3][1001] = {0, };
	int total_cnt[3001] = {0, };
	int total_per_person[100000] = {0, };
	int score_per_person[3][100000] = {0, };


	int total[3001] = {0, };
	cin >> n;
	for(int c = 0 ; c < 3 ; c ++){
		for(int i = 0 ; i < n ; i ++){
			int x; 
			cin >> x;
			cnt[c][x] ++;
			score_per_person[c][i] = x;
			total_per_person[i] += x;
		}
	}
	
	
	for(int i = 0 ; i < n ; i ++) total_cnt[total_per_person[i]] ++;
	
	// cnt 계산
	for(int c = 0 ; c < 3 ; c ++){
		int cur_cnt = 0;
		for(int i = 1000 ; i >= 0 ; i --){
			if(cnt[c][i] == 0) continue;
			int before = cnt[c][i];
			cnt[c][i] = cur_cnt + 1;
			// cout << i << " : " << cnt[c][i] << ' ';
			cur_cnt += before;
		}
		for(int i = 0 ; i < n ; i ++) cout << cnt[c][score_per_person[c][i]] << ' ';
		cout << '\n';
	}
	

	// total 계산
	int cur_cnt = 0;
	for(int i = 3000 ; i >= 0 ; i --){
		if(total_cnt[i] == 0) continue;
		int before = total_cnt[i];
		total_cnt[i] = cur_cnt + 1;
		cur_cnt += before;
	}
	for(int i = 0 ; i < n ; i ++) cout << total_cnt[total_per_person[i]] << ' ';
	cout << '\n';
	return 0;
}

 

주의할 점: 시간복잡도에 대한 생각

 

실시간으로 평가를 치를 때, 난이도가 쉬워보이지만 시간복잡도를 한 번 생각해봐야하는 문제인 것 같았다.

 

먼저 생각해볼 수 있는 관점은 for문을 두 번 돌아서, 각각의 대회에서 참가자 한명마다 다른 참가자 N명을 비교해 나보다 점수가 높은 사람이 몇명인지 알려고한다면 이 코드의 시간복잡도는 O(N^2)이 될 것이다. 참가자 수 N이 100,000까지 올 수 있기 때문에 시간초과가 날 것이라고 생각하였다. 지금 생각하면 두 가지 방법 정도는 존재하는 것 같다.

 

1. 점수별로 cnt 배열을 만들어 해당 점수보다 더 높은 점수를 받은 사람이 몇명인지 누적합을 사용하여 배열을 만든다. 이 경우 누적합을 만들 때 드는 시간 비용이 O(N)이기 때문에 무난하게 시간안에 문제를 풀 수 있으며 위의 코드의 경우이다. 배열의 크기의 경우 가질 수 있는 최대, 최소 점수를 맞추어 설정하였다.

 

2. 배열의 요소를 {점수, 유저 번호} 쌍으로 정렬을 수행한 뒤 순위를 계산하는 것이다. 데이터는 pair<int, int>로 구성되고 크기가 100,000 인 배열을 만들어 점수순으로 sorting을 한 뒤 second의 index에 따라 등수를 복원할 수 있다. 정렬 알고리즘의 경우 O(NlogN)이 들기 때문에 이 방법도 시간안에 들어올 수 있는 문제라고 생각하였다.