[C언어] 18870번 - 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

풀이

좌표 압축이 뭐지..? 검색해도 잘 안나와서 문제 이해를 하는거부터가 어려웠다.

하지만 테스트 케이스의 입/출력을 자세히 보면 입력된 좌표를 오름차순 정렬하고 그 정렬된 배열에서의 인덱스가 출력인걸 알 수 있다.

그리고 이 문제의 시간제한은 2초.. 역시 시간을 아껴써야 한다. 그래서 우선 좌표를 입력 받을 때 origin과 sorted를 나눠서 받고

sorted는 퀵 정렬을 이용해 정렬하기로 했다.

그리고 Merge Sort랑 비슷하다고 생각했던 이진 탐색을 통해 origin의 값이 sorted의 어느 위치에 있는지 찾았다.

근데 값이 이상하게 나왔고 중복 때문인걸 발견하고 중복제거 함수까지 구현했다.. 테스트 케이스는 통과했지만 역시나 '시간초과'..ㅜㅜ

 

삽질을 계속 해봐도 '시간초과'를 벗어나지 못해서 구글링을 통해 팁을 얻었다..

중복 제거할 때 for문이 2중으로 들어가는 부분만 해결하면 될거 같았는데 역시나 그게 정답이었다.....

기존엔 origin, sorted, unique 배열을 각각 만들었었는데 unique 배열을 만들 필요 없이 sorted 배열만 한바퀴 슥 돌면서

head를 기준으로 i를 늘려가며 다른 값을 찾으면 head 앞으로 가져오고 거기를 head로 삼는걸 반복하면 되는거였다 ...

이렇게 하니까 head + 1이 중복제거된 전체 배열 길이여서 따로 구하지 않아도 되고 그걸 갖고 바로 이진 탐색을 할 수 있었다

1차 코드 (실패)

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

//퀵 정렬 오름차순을 위한 비교
int compare(const void *a, const void *b) {
    return *(int*) a - *(int*) b;
}

//이진 탐색
int binary_search(int arr[], int left, int right, int key) {
    int mid = (left + right) / 2;

    if(arr[mid] == key) {
        return mid;
    }
    else if(arr[mid] > key) {
        return binary_search(arr, left, mid - 1, key);
    }
    else {
        return binary_search(arr, mid + 1, right, key);
    }
}

//중복 제거
void unique(int arr[], int arr_uniqued[], int size, int* arr_index) {
    for(int i = 0; i < size; i++) {
        int horse;
        int check = 0;

        for(horse = i + 1; arr[i] == arr[horse]; horse++);

        if(horse > i + 1) {
            arr_uniqued[*arr_index] = arr[horse - 1];
            i = horse - 1;
            *arr_index = *arr_index + 1;
        }
        else {
            arr_uniqued[i] = arr[horse - 1];
            *arr_index = *arr_index + 1;
        }
    }
}

int main(void) {
    //좌표 개수 입력
    int n;
    scanf("%d", &n);

    int arr_index = 0;
    int* arr_origin = (int*) calloc(n, sizeof(int));
    int* arr_sorted = (int*) calloc(n, sizeof(int));
    int* arr_unique = (int*) calloc(n, sizeof(int));

    //좌표 입력
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr_origin[i]);
        arr_sorted[i] = arr_origin[i];
    }

    //퀵 정렬
    qsort(arr_sorted, n, sizeof(int), compare);

    //중복 제거
    unique(arr_sorted, arr_unique, n, &arr_index);

    //arr_origin의 인덱스 0부터 오름차순 정렬된 arr_sorted에서의 인덱스를 이진 탐색을 통해 출력
    for(int i = 0; i < n; i++) {
        printf("%d ", binary_search(arr_unique, 0 , arr_index, arr_origin[i]));
    }

    //메모리 free
    free(arr_origin);
    free(arr_sorted);
    free(arr_unique);

    return 0;
}

2차 코드 (성공)

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

//퀵 정렬 오름차순을 위한 비교
int compare(const void *a, const void *b) {
    return *(int*) a - *(int*) b;
}

//이진 탐색
int binary_search(int arr[], int left, int right, int key) {
    int mid = (left + right) / 2;

    if(arr[mid] == key) {
        return mid;
    }
    else if(arr[mid] > key) {
        return binary_search(arr, left, mid - 1, key);
    }
    else {
        return binary_search(arr, mid + 1, right, key);
    }
}

//중복 제거
int unique(int arr_sorted[], int size) {
    int head = 0;

    for(int i = 1; i < size; i++) {
        if(arr_sorted[head] == arr_sorted[i]) continue;
        arr_sorted[++head] = arr_sorted[i];
    }

    return ++head;
}

int main(void) {
    //좌표 개수 입력
    int n;
    scanf("%d", &n);

    int horse = 0;
    int arr_index = 0;
    int* arr_origin = (int*) calloc(n, sizeof(int));
    int* arr_sorted = (int*) calloc(n, sizeof(int));

    //좌표 입력
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr_origin[i]);
        arr_sorted[i] = arr_origin[i];
    }

    //퀵 정렬
    qsort(arr_sorted, n, sizeof(int), compare);

    //중복 제거
    int len = unique(arr_sorted, n);

    //arr_origin의 인덱스 0부터 오름차순 정렬된 arr_sorted에서의 인덱스를 이진 탐색을 통해 출력
    for(int i = 0; i < n; i++) {
        printf("%d ", binary_search(arr_sorted, 0, len, arr_origin[i]));
    }

    //메모리 free
    free(arr_origin);
    free(arr_sorted);

    return 0;
}