1015번: 수열 정렬

https://www.acmicpc.net/problem/1015


$O(n^2)$

i번째 수의 인덱스는 앞의 수 중 자신 이하인 수의 개수+뒤의 수 중 자신 미만인 수의 개수이다.

#include<stdio.h>
const int MAX_N = 50;
int n, a[MAX_N], b[MAX_N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++) {
        scanf("%d", a + i);
        for (int j = 0; j<i; j++) a[j]>a[i] ? b[j]++ : b[i]++;
    }
    for (int i = 0; i<n; i++) printf("%d ", b[i]);
    return 0;
}