[인프런 C++] 26. 마라톤

장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. ~ 선수들은 자신이 앞으로 얻을 수 있는 최선의 등수를 계산할 수 있다. 각 선수의 평소 실력은 정수로 주어지는데, 더 큰 값이 더 좋은 실력을 의미한다. 더 큰 수를 갖고 있는 사람만 앞지르기 가능하다. 선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아 각 선수의 최선의 등수를 계산하는 프로그램을 작성하시오.

 

입력

8

2 8 10 7 1 9 4 15

 

출력

1 1 1 3 5 2 5 1

 

1트 (80점)

5가지 경우 중 1가지 경우에서 타임리밋

👉 vector의 크기를 n+1로 설정해야 1부터 데이터 init을 할때, 오류가 발생하지 않는다!

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

int main(void){
	freopen("input.txt", "rt", stdin);
	
	int n;
	cin >> n;
	vector <int> a(n);
	vector <int> b(n);
	
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		b[i] = i;
	}
	
	for(int i = 2; i <= n; ++i){
		for(int j = 1; j <= i-1; ++j){
			if(a[j] < a[i]){
				b[i]--;
			}
		}
	}
	
	cout << 1;
	for(int i = 2; i <= n; ++i){
		cout << b[i];
	}
	
	return 0;
}

 

2트 (강의 풀이)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	freopen("input.txt", "rt", stdin);
	int i, j, n, cnt=0;
	scanf("%d ", &n);
	vector<int> a(n+1);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	printf("1 ");
	for(i=2; i<=n; i++){
		cnt=0;
		for(j=i-1; j>=1; j--){
			if(a[j]>=a[i]) cnt++;
		}
		printf("%d ", cnt+1);
	}
	return 0;
}