/<> 백준 18870번 : 좌표 압축 (C언어)

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

 

 

문제에서 주의할 점은, 숫자의 중복을 허용하지 않는다는 점입니다. 따라서 입력받는 수 중 중복되는 수들을 카운트할 때 제외해야 합니다. 

 

 

1. 숫자를 저장할 배열 2개를 생성하여, 하나는 마지막 크기 비교용, 하나는 순서 정렬용으로 사용합니다.

 

2. qsort를 사용해 한 배열을 정렬합니다.

 

3. 중복을 없애기 위해 2단계를 토대로 숫자 종류가 하나씩만 있는 배열을 생성합니다.

 

4. 처음에 만든 나머지 배열을 3단계의 배열과 비교하여 자기보다 작은 숫자가 몇 개인지 비교합니다. 이때 시간복잡도를 줄이기 위해 이진 탐색을 사용합니다.

 

 

<코드>

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

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

int main() {
    int n;
    scanf("%d", &n);
    int num[n];
    int num2[n];
    int unique[n];
    int count[n];
    
    for(int i = 0; i < n; i++) count[i] = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
        num2[i] = num[i];
    }

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

    // 고유한 숫자 배열 생성
    int idx = 0;
    unique[idx++] = num[0];
    for(int i = 1; i < n; i++) {
        if(num[i] != num[i-1]) {
            unique[idx++] = num[i];
        }
    }

    // 각 숫자보다 큰 고유 숫자의 개수를 계산
    for(int i = 0; i < n; i++) {
        int left = 0, right = idx - 1, mid;
        while(left <= right) {
            mid = (left + right) / 2;
            if(num2[i] > unique[mid]) left = mid + 1;
            else right = mid - 1;
        }
        count[i] = left;
    }

    for(int i = 0; i < n; i++) printf("%d ", count[i]);
    printf("\n");

    return 0;
}

 

 

풀면서 계속 시간 초과가 떴던 문제였습니다. qsort와 이진 탐색을 잘 활용해야겠습니다.