distinct hint

1. O(n) 으로 구현 하기

#include <stdio.h>

int main()
{
   int a[1001]={0};
   int i,tmp,ans;
   int n;

   scanf("%d",&n);

   for( i = 1 ; i <= n ; i++){
      scanf("%d",&tmp);
      a[tmp] = 1; // 배열의 인덱스를 수로 사용
   }

   ans = 0;
   for( i = 1 ; i <= 1000 ; i++){
      if ( a[i] == 1 ) {
         ans++;
      }
   }

   printf("%d\n",ans);
}

2. O(nlogn) 으로 구현 하기

1. 데이터를 정렬 합니다.(logn 시간 복잡도)
2. 데이터를 하나씩 가져와서 원하는 데이터가 있는가를 이진 검색을 사용합니다.(nlogn)

#include <stdio.h>

void Quick_Sort(int numbers[], int array_size)
{
   q_sort(numbers, 0, array_size - 1);
}

void q_sort(int numbers[], int left, int right)
{
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = numbers[left];
   while (left < right)
   {
     while ((numbers[right] >= pivot) && (left < right)) right--;
     if (left != right)
     {
       numbers[left] = numbers[right];
       left++;
     }
     while ((numbers[left] <= pivot) && (left < right)) left++;
     if (left != right)
     {
       numbers[right] = numbers[left];
       right--;
     }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot) q_sort(numbers, left, pivot-1);
   if (right > pivot) q_sort(numbers, pivot+1, right);
}

int main()
{
   int i, n, ans=0;
   int arr[1001];
   scanf("%d", &n);
   for(i=0; i < n;i++) scanf("%d", &arr[i]);
   Quick_Sort(arr, n);
   for(i=0;i < n;i++)
   {
      if(i > 0)
      {
         if(arr[i]==arr[i-1]) continue;
      }
      ans++;
   }
   printf("%d\n",ans);
}
   

*소스 출처:pl0892029

3. O(n^2) 으로 구현 하기

#include <stdio.h>

int main()
{
   int a[1001];
   int i,j,tmp;
   int n,last;

   scanf("%d",&n);

   last = 0;
   for( i = 1 ; i <= n ;i++){
      scanf("%d",&tmp);

      for( j = 1 ; j <= last ; j++){
         if ( a[j] == tmp ) {
            break;
         }
      }

      if ( j > last ) {
         last++;
         a[last] = tmp;
      
      }
   }

   printf("%d\n",last);
}