BOJ 10867 (중복 빼고 정렬하기)

• 문제
  N개의 정수가 주어진다. 이때, N개의 정수를 오름차순으로 정렬하는 프로그램을 작성하시오. 같은 정수는 한 번만 출력한다.
  
  
• 입력
  첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다.
  
  
• 출력
  첫째 줄에 수를 오름차순으로 정렬한 결과를 출력한다. 이때, 같은 수는 한 번만 출력한다.

#include<iostream>
#include<algorithm>
using namespace std;
int N;
int arr[100001];
void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
}

int main() {
	fast_io();
	input();
	sort(arr, arr + N);
	cout << arr[0] << ' ';
	for (int i = 1; i < N; i++) {
		if (arr[i] == arr[i - 1]) {
			continue;
		}
		cout << arr[i] << ' ';
	}
	return 0;
}

   정렬 후 중복된 문자만 제거해주면 되는 간단한 문제이지만 입력 받는 수가 절댓값이 1000보다 작거나 같은 정수 이므로 음수가 들어올 수 있다는 것에 주의를 해야한다.

입력 받은 배열을 오름차순 정렬 후 이전의 값과 같다면 넘기고 다르다면 출력하여 중복을 제거했다.

시간 복잡도 : O(NlogN)

숏코딩

#include<iostream>
int a[2001]={0};
int main() {
    int x,n;std::cin>>n;while(n--){
        std::cin>>x;a[x+1000]++;
    }for(int i=0;i<2001;i++)
    	if(a[i])
   		 std::cout<<i-1000<<" ";
}

숫자를 10만개 입력 받지만 중복을 제거 하므로 배열의 크기가 2000이면 충분하다.
음수를 고려하여 +1000을 해서 1000 미만의 숫자를 음수료 표현하고 초과는 양수로 표현하였다.