[C] 백준 18870번 : 좌표 압축

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

18870번: 좌표 압축

---

문제 풀이

 1. 값들을 n회 입력받는다. 일반 배열과 정렬시킬 배열을 위해 또 다른 배열에 같이 저장한다. 이 때, 정렬된 배열은 나중에 값을 비교하는데 쓰인다.

 2. qsort를 통해서 배열을 정렬하고 unique로 다시 재정렬 및 인덱스를 리턴한다. 

 3. 일반 배열(arr)과 중복 없이 정렬된 배열(sort)을 비교하여 일반 배열의 값들이 몇번째 인지 출력한다. 좌표의 수가 최대 10^6의 경우이므로 시간복잡도를 줄이기 위해서 이진 탐색(binary search)를 사용한다.

느낀점

 너무 어렵게 풀은 알고리즘이다. 처음 좌표 압축이란 개념도 다른 분들의 글을 통해서 이해했고 시간 초과가 계속나자 다른 분들의 코드를 참고하고 싶었지만 구글링해서 찾을 수 있는 코드들은 오직 C++ 코드 뿐이었다. 그래서 계속 허우적거리다가 C++의 unique 함수를 이해하고 이진 탐색 등의 방법으로 최대한 시간복잡도를 최소화하였다.

  보통 이진 탐색에서 값을 못 찾을 경우 -1을 리턴하는데, 나는 일반 배열과 정렬된 배열이 근본적으로 같은 값을 가지므로 못 찾을 경우를 제외시켰다. 

 이번 문제로 python과 c++로 넘어가고자하는 마음이 굳어졌다...!!

코드

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

int compare(const void* a, const void* b) {
	return *(int*)a - *(int*)b;
}

int unique(int* arr, int size) {
	int i, j = 0;
	for (i = 1; i < size;i++) {
		if (arr[j] == arr[i]) continue;
		arr[++j] = arr[i];
	}
	return ++j;
}

int binarysearch(int* arr, int size, int key) {
	int left = 0, right = size - 1, mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (arr[mid] < key) left = mid + 1;
		else if (arr[mid] > key) right = mid - 1;
		else return mid;
 	}
}

int main() {
	int n;
	scanf("%d", &n);

	int* arr = (int*)calloc(n, sizeof(int));
	int* sort = (int*)calloc(n, sizeof(int));

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

	qsort(sort, n, sizeof(int), compare);

	int cnt = unique(sort, n);
	for (int i = 0;i < n;i++) {
		int tmp = binarysearch(sort, cnt, arr[i]);
		printf("%d ", tmp);
	}
	free(arr);
	free(sort);

	return 0;
}