백준 18870 : 좌표 압축

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

18870번: 좌표 압축

 

푸는데 뒤지게 오래걸렸다.

접근 방법이 어려웠다기보단 구현이 어려웠다.

 

이 문제를 풀면서 가장 어려웠던건 바로 범위가 엄청나게 크다는 것 인데,

덕분에 여러가지 최적화를 학습할 수 있었다.

 

이 문제는 3가지정도를 떠올려야 하는데,

1. 인덱싱

2. 중복제거(unique)

3. 이분탐색

되시겠다.

 

전체적으로 생각한건 일단 입력배열에 값을 받고, 이를 새로운 배열에 퀵솔트한다.

그리고 그 두 배열을 비교하여, 정렬이 된 배열의 인덱스를 찾아 출력해 주려고 했다.

여기서 인덱싱이 사용되었고

 

입력 배열에 중복되는 값들이 많을 경우 인덱싱이 어렵다. 따라서 정렬된 배열에서

중복된 값들을 지워준다. 문제는 이게 c++에는 unique라고 따로 있는데

대단한 c언어에서는 그딴게 없기때문에 self로 구현하셔야한다. 여기서 중복제거 사용

 

마지막으로 정렬된 배열과 input 배열을 비교하여 값을 출력한다.

여기서 for문 두개 겹쳐서 하나하나비교하면 당연히 시간 오버가 나온다.

그렇기때문에 여기에서 이분탐색이 사용된다.

 

그렇게 짠 코드는 다음과 같다.

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

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

int unique(int *res, int size) {
    int i, j = 0;

    for(i=1;i<size;i++) {
        if(res[j] == res[i])
            continue;
        res[++j] = res[i];
    }

    return ++j;
}

int binarysearch(int *res, int size, int key) {
    int low = 0, high = size - 1, mid;

    while(low <= high) {
        mid = (low + high) / 2;
        if(res[mid] < key)
            low = mid + 1;
        else if(res[mid] > key)
            high = mid - 1;
        else
            return mid;
    }
}

int solve() {
	int test;
	scanf("%d", &test);
	
	int input[test], rank[test];
	for(int i=0;i<test;i++) {
		scanf("%d", &input[i]);
		rank[i] = input[i];
	}
	
	qsort(rank, test, sizeof(int), compare);
    
    int cnt = unique(rank, test);
    for(int i=0;i<test;i++) {
        int temp = binarysearch(rank, cnt, input[i]);
        printf("%d ", temp);
    }
	printf("\n");
	
}

int main() {
	solve();
	return 0; 
}

더러운 c언어련,,

이젠 자바스크립트 공부해서 자바스크립트로 할거다,, 너무 짤게 많아서 힘들다