문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

Naive 하게 풀면, 매번 각 선수 앞에서 달리고 있는 선수들의 실력을 조사하여 최선의 등수를 구할 수 있다. 그러나, 이는 시간 복잡도가 O(N^2)이다. 조사를 진행하면서, 앞에 특정 선수가 존재하는 걸 이미 확인했는데, 다시 체크하는 것은 불필요한 계산이다. 이러한 중복 체크를 피하기 위해, 등수대로 거쳐가면서 해당 실력 선수의 존재 여부를 체크해 준다면, 현재 조사하는 선수보다 실력이 낮은 선수들 중, 존재가 확인된(=앞서 있는) 선수의 개수만 세주면 된다.

Algorithm

선수 실력을 index로 하는 Segment Tree를 만들어, 각 실력 구간에 몇명의 선수가 존재하는 지 저장한다.
(이때, 실력의 범위가 너무 크기 때문에, 선수의 크기만큼 압축해 준다. 압축은 정렬을 통해 순서대로 0부터 N-1 까지로 정해주면 된다.)

선두부터 꼴등까지 거쳐가며 아래의 논리를 따른다.
1. 현재 선수보다 앞서 확인된, 낮은 레벨 구간의 선수 수를 ST로 확인한다.
2. 현재 선수를 존재하는 선수로 ST에 +1 해준다.

Data Structure

• Segment Tree[]: 선수들의 실력을 index로 하여, 존재 여부를 구간합으로 저장.

결과

Other

시간 복잡도는 O( nlogn ) 이다.