26. 마라톤 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

#include<stdio.h>
#include<vector>

using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	
	vector<int> rank(n+1, 0);
	for(int i = 1; i < n+1; i++)
		scanf("%d", &rank[i]);
	
	vector<int> goal(n+1, 0);
	for(int i = 1; i < n+1; i++)
	{
		int num = i;
		if(i == 1)
		{
			goal[i] = num;
			continue;
		}
		for(int j = i-1; j >= 1; j--)
		{
			if(rank[i] > rank[j])
				num--;
		}
		goal[i] = num;
	}
	
	for(int i = 1; i < n+1; i++)
		printf("%d", goal[i]);
		
	return 0;
}

1. 1부터 n+1까지의 0으로 초기화된 vector 선언

 

                        start ↓ ( idx = 1, num = 1) -> goal[1] = 1;

0

2

8

10

7

1

9

4

15

idx 1부터 시작해서 왼쪽으로 진행하면서 비교한다.

num은 idx부터 시작하고, start에 있는 수보다 큰 수를 만날 때마다 num에서 1을 차감한다.

마지막 idx인 1까지 비교가 끝났을 때, num을 goal[idx]에 할당한다.

 

                                             start ↓ ( idx = 2, num = 2) -> goal[2] = 2 - 1(2가 8보다 작기 때문) = 1;

0

2

8

10

7

1

9

4

15

                                                                   start ↓ ( idx = 3, num = 3) -> goal[3] = 3 - 2(2, 8이 10보다 작기 때문) = 1;

0

2

8

10

7

1

9

4

15

                                                                                        start ↓ ( idx = 4, num = 4) -> goal[4] = 4 - 1(2만 작기 때문) = 3;

0

2

8

10

7

1

9

4

15