[C++]Softeer/HSAT Level3 - 성적 평가

<문제>

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

Softeer

현주는 N명의 인원이 참여하는 프로그래밍 스터디 그룹을 이끌고 있다.

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

현주는 각 대회별 등수 및 최종 등수를 매기고 싶다. 등수는 가장 점수가 높은 사람부터 1등, 2등, ···, N등의 순서대로 붙는다. 만일 동점이 있을 경우 가능한 높은 (등수의 수가 작은) 등수를 부여한다. 즉, 점수가 내림차순으로 10,7,6,6,4의 순서일 경우, 6점을 받은 두 사람은 공동 3등이 되고, 그 다음 순서인 4점을 받은 사람은 5등이 된다. 이 규칙을 다르게 표현하면 다음과 같다: 각 사람마다 “나보다 점수가 큰 사람”의 수를 세어 1을 더한 것이 자신의 등수가 된다. 대회별 등수는 각 대회에서 얻은 점수를 기준으로 하며 최종 등수는 세 대회의 점수의 합을 기준으로 한다.

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

제약조건
3 ≤ N ≤ 100,000

 

<제출답안>

이 문제는 상당히 킹 받는다.

첫째 분명 문제는 이해가 됐는데 풀이법이 제대로 생각이 안났다.

copy용 array를 만들어서 복사해두고 copy array를 sort한뒤 원래 array 에서 순서대로 find를 쓰면 되지 않을까 싶었는데 find 함수는 몇번을 반복해도 찾고자하는 것과 맨처음 만난 원소를 return하기 때문이다.

가령 나는 'baabc' 를 copy한뒤 sort해서 'aabbc' 를 만들어낸뒤 '12034' 식의 값을 얻어내고 싶은거다.

그런데 find함수를 쓰면 킹받아버리게도 '11004' 식의 값이 나오는거다.

그래서 그런 바보같은 풀이는 재쳐두고 도저히 이 미개한 머리에선 답이 안나와서, 

구글링을 해보았다.

 

시도1(오답)

구글링을 하다가 누가 파이썬으로 코드를 올려놓은것을 봤다.

그분은 그냥 자기 자신보다 점수가 큰 사람이 있다면 등수를 +1 하는 풀이로 푸셨다.

왜냐면 지금 문제에서 등수의 개념이 본인보다 점수높은 사람들의 수 +1 이니까 말이다.

그래서 나는 다음과 같이 문제를 풀었다.

 

(아래 풀이는 완전탐색으로 timeout이 난다. 다음과 같이 풀면 안된다.

그냥 복기용으로 써둔것이므로 주의깊게 보지 않아도된다.)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N;
int arr[4][100100];

int main(int argc, char** argv)
{
	
	cin>>N;
	
	// 점수 값 입력받기
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<N;j++)
		{	
			cin>>arr[i][j];
			arr[3][j] += arr[i][j] ;
		}
	}

	// 등수 매기기 (0~N 까지 돌면서 자기자신보다 점수가 큰 사람이 있다면 +1 해준다.)
	for(int i=0;i<4;i++)
	{
		
		int answer[N] = {0,};	
		for(int j=0;j<N;j++)
		{
			for(int k=j;k<N;k++)
			{
				if(arr[i][j]<arr[i][k])
					answer[j]++;
				else if(arr[i][j]>arr[i][k])
					answer[k]++;
			}
		}
		
		for(int j=0;j<N;j++)
		{
			cout<<answer[j]+1;
			cout<<" ";
		}	
		cout<<"\n";
	}

	return 0;
}

결과는 말했듯 timeout..

갑자기 너무 현타가 왔다. 심지어 원래는 k도 j부터 하지않고 0부터 했는데,

혹시 너무 많이 탐색해서 그런가 하고 k를 j부터 시작하고 if ~ else if 로 변경해준건데도(버블 sort개념처럼) 타임아웃이 나왔다.

엥? 시험언어를 파이썬으로 바꿔야하나 하면서 블로거 파이썬 답안을 그대로 따라적었는데 timeout이 났다..

?????? 아니 통과를 안된 답안을 올려주셨던거다..

아놔.. 혹시나.. 내 블로그 보다가 그런 일이 발생한다면 꼭 누가 댓글좀 남겨주시길 바란다.

그래서 난 다시 C++로 어떤 방식으로 풀어야할지 고민을 해봤다..

 

...............................................

.......................

...

 

시도 2(정답)

문득! 풀이가 머리에 떠올랐다. 통근버스 문제처럼 누적합 DP로 구현해보면 어떨까? 하는 생각이었다.

(참고로 통근버스 문제 풀이는 아래와 같다.)

https://carcode.tistory.com/51

Softeer/HSAT Level3 - 통근버스 출발 순서 검증하기

 

비슷한 개념으로 적용해본다.

일단, 0점 부터 3000점 까지 각 점수별로 사람수를 세준다.

그 다음에 각 점수별로 그 위의 점수가 몇명인지 센다.

그 후 현재 점수 바로 위 점수 사람수 + 1 로 답을 내준다.

이렇게되면 최대 100,000 *100,000 의 시간복잡도를 갖던 문제가

100,000 + (100,000 + 3,000 +100,000) * 3 으로 줄어들 수 있는 것이다,, ㅎㅎ

 

#include<iostream>
#include<vector>
#include<algorithm>
#include <cstdint>
#include <cstring>

using namespace std;

int N;
int arr[4][100100];

int main(int argc, char** argv)
{
	
	cin>>N;
	
	// 점수 값 입력받기
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<N;j++)
		{	
			cin>>arr[i][j];
			arr[3][j] += arr[i][j] ;
		}
	}
	
	int person_per_score[102]   = {0,};
	int person_above_score[102] = {0,};

	for(int j=0;j<N;j++)
		person_per_score[arr[0][j]]++;
	
	for(int i=0;i<4;i++)
	{
		int person_per_score[3002]   = {0,};
		int person_above_score[3002] = {0,};
		
		//각 점수별로 사람수를 세준다.
		for(int j=0;j<N;j++)
			person_per_score[arr[i][j]]++;

		//각 점수별로 그 위의 점수가 몇명인지 센다.
		for(int k=3000;k>=0;k--)
		{
			if(person_per_score[k+1] == 0)
				person_above_score[k] = person_above_score[k+1];
			else
				person_above_score[k] = person_above_score[k+1]+person_per_score[k+1];
		}

		//현재 점수 바로 위 점수 사람수+1 로 답을 내준다.
		for(int j=0;j<N;j++)
		{
			cout<<person_above_score[arr[i][j]]+1;
			cout<<" ";
		}	
		cout<<" "<<endl;

	}
	return 0;
}

이렇게 해서 통과,, ㅎㅎ

합격하고 싶다 ㅎㅎ 행복하다.