[C] 중복 되지 않은 원소의 개수 세기

\(O(n^2)\)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
int main() {
    int n, ans = 0; scanf("%d", &n);
    int *arr = (int *)malloc(n * sizeof(int));
    assert(arr != NULL);
    for (int i = 0; i < n; i++) scanf("%d", arr + i);
    for (int i = 0; i < n; i++) {
        int good = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] == arr[i]) good = 0;
        }
        ans += good;
    }
    printf("%d\n", ans);
    return 0;
}

\(O(n\log n)\)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void mergesort(int *, int, int);
void merge(int *, int, int, int);
int main() {
    int n, ans = 1; scanf("%d", &n);
    int *arr = (int *)malloc(n * sizeof(int));
    assert(arr != NULL);
    for (int i = 0; i < n; i++) scanf("%d", arr + i);
    mergesort(arr, 0, n - 1);
    for (int i = 1; i < n; i++) ans += arr[i] != arr[i - 1];
    printf("%d\n", ans);
    return 0;
}
void mergesort(int *arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergesort(arr, left, mid);
    mergesort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}
void merge(int *arr, int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    int *tmp = (int *)malloc((right - left + 1) * sizeof(int));
    assert(tmp != NULL);
    while (i <= mid && j <= right) tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    while (k--) arr[left + k] = tmp[k];
    free(tmp);
}