๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โœจ Algorithm

[๋ฐฑ์ค€/C++] 10876๋ฒˆ : ์ค‘๋ณต ๋นผ๊ณ  ์ •๋ ฌํ•˜๊ธฐ

by nitronium102 2021. 9. 8.

๋ฌธ์ œ

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 ๊ตฌ์กฐ์ด๊ธฐ ๋•Œ๋ฌธ)

๋Œ“๊ธ€