baekjoon 18870

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

---

Idea

우선 좌표압축이란 말을 제대로 이해해야 한다.
참고 : https://medium.com/algorithms-digest/coordinate-compression-2fff95326fb

대충 뭐 머신러닝의 데이터 전처리의 피처 스케일링(Feature scaling)과 느낌이 비슷하다.
입력되는 Xi의 값의 범위는 -10^9 ≤ Xi ≤ 10^9이기 때문에 매우 크다. 만약 이 값을 그대로 반영해서 문제를 푼다고 하면 배열의 크기가 감당할 수 없을 만큼 커지게 되고 결국 시간초과와 메모리 부족을 불러올 것이다. 그걸 유도하고 좌표압축이란 알고리즘을 쓰란 거겠지만..

쨌든 Xi 값보다 그 값에 고유한 순서 정수를 부여하고 그 순서를 출력하란 말 같다.
순서를 알기 위해선 정렬을 해야한다. 그 전에 정렬을 한 후 출력할 때 원래 배열의 순서를 가지고 있어야 하기 때문에 dp배열에 그대로 값을 넣었다.
qsort를 써서 정렬한 후 중복된 수를 제거해준다.
제거한 후 원래 배열의 값을 가지고 있는 dp배열의 원소와 정렬하고 중복된 정수를 지운 배열을 이진탐색 하여 정렬된 배열의 인덱스 값과 원래 배열의 값이 같을 경우 그 정렬된 배열의 인덱스 값을 출력해주면 된다.

말이 좀 어려운데 정리하자면

1. 정렬 할 배열, 값을 그대로 놔둘 배열 두 개를 선언하고 한 개의 배열에 입력을 받는다.
2. 정렬 후 중복된 값을 지운다.
   | 2 | 4 | -10 | 4 | -9 | -> | -10 | -9 | 2 | 4 | 4 | -> | -10 | -9 | 2 | 4 |
3. 정렬하지 않은 배열의 요소를 key값으로 잡고 정렬 된 배열에서 같은 값을 찾으면 그 인덱스를 출력한다.

---

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b);
int unique(int* arr, int N);
int binarySearch(int arr[], int N, int key);

int main(void) {
	int N;

	scanf("%d", &N);

	int* arr = (int*)calloc(N, sizeof(int));
	int* dp = (int*)calloc(N, sizeof(int));

	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
		dp[i] = arr[i];
	}

	qsort(arr, N, sizeof(int), compare);

	int idx = unique(arr, N);

	for (int i = 0; i < N; i++) {
		printf("%d ", binarySearch(arr, idx + 1, dp[i]));
	}

	return 0;
}

int compare(const void* a, const void* b) {
	int A = *(int*)a;
	int B = *(int*)b;

	if (A < B) {
		return -1;
	}
	if (B < A) {
		return 1;
	}

	return 0;
}

int unique(int* arr, int N) {
	int result = 0, first = 0, last = N;
	int temp = 0;

	while (first != last) {
		if (arr[result] == arr[first]) {
			first++;
		}
		else {
			result++;
			arr[result] = arr[first];
		}
	}

	return result;
}

int binarySearch(int arr[], int N, int key) {
	int low = 0, high = N - 1;
	int mid;
	
	while (low <= high) {
		mid = (low + high) / 2;
		if (key == arr[mid]) {
			return mid;
		}
		else if (key < arr[mid]) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
}