[알고리즘/문제풀이/BOJ 18870번] 좌표 압축

원래 좌표, 압축된 좌표, 순서를 저장할 수 있도록 구조체를 선언한 후 처음에는 원래 좌표를 기준으로 정렬하여 압축된 좌표를 찾고, 그 후 입력받은 순서대로 정렬하여 압축된 좌표를 문제의 답과 같은 순서로 출력할 수 있도록 하였습니다. 

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#include<stdlib.h>

int N;

typedef struct point {
	int x;
	int x_;
	int order;
} POINT;

POINT points[1000020];

int compare(const void* first, const void* second) {
	if (((POINT*)first)->x < ((POINT*)second)->x)
		return -1;
	else if (((POINT*)first)->x > ((POINT*)second)->x)
		return 1;
	else
		return 0;
}

int compare1(const void* first, const void* second) {
	if (((POINT*)first)->order < ((POINT*)second)->order)
		return -1;
	else if (((POINT*)first)->order > ((POINT*)second)->order)
		return 1;
	else
		return 0;
}

int main(void) {

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &points[i].x);
		points[i].order = i;
	}

	qsort(points, N, sizeof(POINT), compare);

	for (int i = 0; i < N; i++) {
		
		if (i == 0) {
			points[i].x_ = 0;
		}
		else {
			if (points[i - 1].x == points[i].x) {
				points[i].x_ = points[i - 1].x_;
			}
			else {
				points[i].x_ = points[i - 1].x_+1;
			}
		}
	}

	qsort(points, N, sizeof(POINT), compare1);

	for (int i = 0; i < N; i++) {
		printf("%d ", points[i].x_);
	}
	printf("\n");
}

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