[C/C++] 마라톤

문제

KSEA 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자
기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지
르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면
남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을
수 있는 최선의 등수를 알 수 있다.
각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고
있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면
각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 예
를 들어, 4번째로 달리고 있는 평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평
소 실력이 2인 선수만 앞지르는 것이 가능하고 평소실력이 8과 10인 선수들은 앞지르는 것이
불가능하므로, 최선의 등수는 3등이 된다.
선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산
하는 프로그램을 작성하시오.

 

입력설명
첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음
줄에는 N개의 정수가 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수
부터 제시한 것이다. 각 정수는 1 이상 100,000 이하이다. 참가한 선수의 평소실력은 같을 수
있습니다. 그리고 실력이 같다면 앞에 달리는 선수를 앞지를 수 없습니다.

 

출력설명
각 선수의 최선의 등수를 나타내는 정수 N개를 입력에 주어진 선수 순서와 동일한 순서로 한
줄에 출력한다. 모든 정수들 사이에는 하나의 공백을 둔다.

문제 풀이

이중 for문을 통해 등수를 탐색하는 문제임. 해가 존재할 것으로 보이는 모든 경우의 수를 탐색하는 것으로 일종의 브루트포스 알고리즘이라고 할 수 있음.

 

첫 번째, 해당 선수의 현재 등수를 기록한다. 이는 cur_rank = i+1;로 기록할 수 있음.

두 번째, 앞에 있는 선수가 실력이 낮을 경우 등수를 하나씩 감소 시킴. 이 때 실력이 낮은 선수를 세고 그 때마다 등수를 감소시키면 됨.

	for (int i=1; i<n; i++)
	{
		cur_rank=i+1;
		for (int j=0; j<i; j++)
		{
			if (arr[j]<arr[i]) cur_rank--;
		}
		rank[i]=cur_rank;
	}

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10010
using namespace std;


int main()
{
	int n=0;
	int cur_rank=0;
	int arr[MAX]={0,};
	int rank[MAX]={0,};
	
	cin>>n;
	
	for (int i=0; i<n; i++)
	{
		cin>>arr[i];
	}
	
	rank[0]=1;
	
	for (int i=1; i<n; i++)
	{
		cur_rank=i+1;
		for (int j=0; j<i; j++)
		{
			if (arr[j]<arr[i]) cur_rank--;
		}
		rank[i]=cur_rank;
	}
	
	for (int i=0; i<n; i++)
	{
		cout<<rank[i]<<" ";
	}
		
	return 0;
}

Reference

it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비