[C]백준 12.정렬: 18870

백준 18870

내코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct _X {
	int x;
	int index;
	int result;
} x;

int compare_x(const void* first, const void* second) {
	x a = *(x*)first;
	x b = *(x*)second;
	if (a.x < b.x)
		return -1;
	else if (a.x > b.x)
		return 1;
	else
		return 0;
}
int compare_index(const void* first, const void* second) {
	x a = *(x*)first;
	x b = *(x*)second;
	if (a.index < b.index)
		return -1;
	else if (a.index > b.index)
		return 1;
	else
		return 0;
}
int main() {
	int n;
	scanf("%d", &n);
	x* arr = malloc(sizeof(x) * n);
	for (int i = 0; i < n; i++) {
		arr[i].index = i;
		arr[i].result = 0;
		scanf("%d", &arr[i].x);
	}
	qsort(arr, n, sizeof(x), compare_x);
	int cnt = 0;
	for (int i = 1; i < n; i++) {
		if (arr[i - 1].x != arr[i].x) {
			cnt++;
			arr[i].result = cnt;
		}
		else {
			arr[i].result = cnt;
		}
	}
	qsort(arr, n, sizeof(x), compare_index);
	
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i].result);
	}
	
	return 0;
}

구조체와 qsort를 이용해 풀었다.
전체적인 풀이 방식은 좌표 값을 기준으로 정렬하여 xi<xj를 만족하는 서로 다른 좌표의 개수를 구하고, 그 개수를 입력된 순서대로 출력하였다.
그래서 좌표값을 x, 입력된 순서를 index, xi<xj를 만족하는 서로 다른 좌표의 개수를 result로 하여 구조체에 저장하였다.

좌표 값을 기준으로 정렬하는 compare_x함수를 작성하였고 compare_x 함수로 정렬한 다음에는 각 배열의 result 값을 설정해 줬다. 반복문을 통해 정렬된 배열을 0부터 돌며 앞 인덱스 배열의 x값과 다르지 않다면 cnt를 배열의 result에 저장하고, 그 외엔 cnt를 1증가시킨다음 result에 저장했다.
그 후 다시 배열을 입력된 순서 기준으로 정렬하는 compare_index 함수를 통해 정렬하였고, 배열의 result값을 순서대로 출력하였다.