정렬한 위치와 원래 위치를 함께 읽어요
앞 레슨에서 정렬 후 k번째 값을 읽었어요. 이번에는 원래 순서를 유지하면서 각 값의 순위를 반환해요. 큰 값일수록 좋은 순위라 큰 값부터 정렬해 볼 수 있어요.
vector<int> ordered=values;는 값을 복사해요. ordered를 정렬해도 원래 values의 순서는 유지돼요. reverse(begin,end)는 그 범위를 뒤집으므로 오름차순 정렬 뒤 쓰면 내림차순이에요.
같은 값 앞의 큰 값만 세요
값 {40,80,80,20}에서 큰 값 순서는 {80,80,40,20}이에요.
| 원래 값 | 더 큰 원소 개수 | 순위 |
|---|---|---|
| 40 | 2 | 3 |
| 80 | 0 | 1 |
| 80 | 0 | 1 |
| 20 | 3 | 4 |
동점 두 개를 각각 1·2위로 나누지 않아요. 두 개가 공동 1위면 다음 값은 3위예요. 원래 첫 값 40의 결과가 최종 vector의 첫 원소에 남아야 해요.
직접 풀어봐요
values의 각 원소에 대해 그 원소보다 큰 원소의 개수+1을 순위로 정의해요. 같은 값은 같은 순위이고 큰 원소는 중복되어 있어도 각각 하나로 세요. 순위들을 원래 원소 순서로 반환해요.
길이는 0100, 원소는 −10001000이에요. 빈 입력은 빈 결과예요. 실행용 입력은 n과 n개 원소, 출력은 순위를 공백으로 구분한 한 줄이며 빈 결과는 빈 줄이에요. 하네스가 입출력을 처리해요.
예시 1: values={4,9,9,1} → [3,1,1,4]. 9 두 개는 공동 1위, 4는 3위예요.
예시 2: values={8,5,2} → [1,2,3]. 큰 값부터 서로 다른 순위를 가져요.
예시 입력
4 4 9 9 1
예상 결과
3 1 1 4
예시 입력
3 8 5 2
예상 결과
1 2 3
핵심 개념
basic-sort-search: 동점 순위와 원래 위치의 결과를 함께 유지해요.