[백준/C++] 10876번 : 중복 빼고 정렬하기

문제

N개의 정수가 주어진다. 이때, N개의 정수를 오름차순으로 정렬하는 프로그램을 작성하시오. 같은 정수는 한 번만 출력한다.

입력

첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 수를 오름차순으로 정렬한 결과를 출력한다. 이때, 같은 수는 한 번만 출력한다.

풀이

set을 이용하자! (set 설명은 아래에...)

#include <iostream>
#include <set>
using namespace std;

int main(){
  int n, k;
  set<int> s;

  cin >> n;
  while(n--){
    cin >> k;
    s.insert(k);
  }

  for (auto iter=s.begin(); iter!=s.end(); iter++){
    cout << *iter << " ";
  }
}

---

 

Set

- 다양한 자료형의 데이터를 저장(key)

- key값을 중복 없이 저장

- key값을 정렬된 상태로 저장

- 검색, 삽입, 삭제에서의 시간 복잡도는 O(logn)

- 랜덤한 인덱스의 데이터에 접근 불가(BST 구조이기 때문)