[백준 / C언어] 18870번 문제

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 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

코드

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

int compare(const void *a, const void *b) {
    int num1 = *(int *)a;
    int num2 = *(int *)b; 

    if (num1 < num2)    return -1;      
    if (num1 > num2)    return 1; 
    return 0;
}

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // 찾지 못한 경우
}

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

    int x[1000000];
    int x_temp[1000000];

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

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

    int newSize = 0;
    for (int i = 0; i < N; i++) {
        if (i == 0 || x_temp[i] != x_temp[i - 1]) {
            x_temp[newSize] = x_temp[i];
            newSize++;
        }
    }

    for (int i = 0; i < N; i++) {
        int index = binarySearch(x_temp, newSize, x[i]);
        printf("%d ", index);
    }

    return 0;
}

처음에 문제를 봤을 때에는 간단하게 배열2개를 활용하고 버블정렬을 사용하여 배열들끼리 비교해서 순서를 정하는 문제인줄 알았다.
후에 문제는 예시 입력에는 올바른 출력값들이 나오지만 "제한" 에 나오는 수들이 큰 나머지 cost가 오버되어 시간초과로 판정되었다.

이 문제를 해결하기 위해 사용된 방법은 크게 2가지이다.
1. binary search (이진 탐색)
2. qsort

먼저 binary search란 배열의 중앙에 있는 값을 알아내어 찾고자 하는 항목이 중앙의 왼쪽에 있는지 오른쪽에 있는지를 알아내어 탐색의 범위를 반으로 줄이는 방법이다.
이 경우 O (Log N) 의 시간 복잡도를 갖게된다.

다음으로 qsort는 ivot을 정하고 pivot보다 작은 값들을 pivot의 왼쪽 pivot보다 큰 값들은 pivot의 오른쪽으로 위치시키고 pivot의 왼쪽 값들과 오른쪽 값들을 각각 따로 또 재귀를 통해 분할정복하는 것을 의미한다.
이 경우 O(nLogN)의 성능을 보이는 정렬 알고리즘이다. 기본적으노 stdlib.h 에서 qsort 함수를 제공해준다.

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *)

• 함수명 : qsort
• 헤더파일 : stdlib.h
• 리턴타입 : void
• 매개변수 : (정렬할 배열, 배열의 원소 개수, 배열 한 칸의 크기, 비교를 수행할 함수 포인터)
• 이용목적 : quick sort를 쉽게 사용할 수 있다.