250318 - set과 백준 25757번

어떤. 사람이랑 같이 문제 풀었는데 set 써서 해결했다니까 너 set 도 아냐..는 발언을 했다.

날 아직도 스타벅스에서 브론즈 3 문제 풀면서 질문하던. 인간으로 기억하는 듯 왜이러셔

억울해서 안 되것다 정리 start

1. set

set은 RED-BLACK 트리로 만들어져있다.

- 1. 중복을 없애며

- 2. 삽입하는 순서에 상관 없이 정렬되서 입력이 된다.

-> 삽입과 삭제가 용이, 자료 찾는 것도 괜찮지만 정렬이 되기 떄문에 입력된 순서가 중요한 문제에선 사용하지 않는 게 좋겠다

 

set <int> s;
s.insert(1);

 

- s.begin()

- s.end()

- s.empty()

- s.size()

 

 

- s.erase(1) : 요소 '1' 삭제

- s.swap(s1, s2) : s1와 s2 교환

- s.clear()

 

+ set 을 pair 로 쓰고 싶다면?

set<pair<int, int>> s3;
s3.insert(make_pair(1, 2));

 

2. multiset

: 중복된 원소를 저장할 수 있다는 점 외에는 set과 동일한 특성을 가짐

 

* 단점 : 데이터 삽입 시 이진 탐색 트리 재조정이 필요해서 속도가 느릴 수 있음

 

=> 이진 탐색 트리로 구현되어 있어 접근/검색/삽입/삭제 모두 O(logN) 소요

 

+ 그렇다면 vector 는? 당연히 O(N) 이기 때문에

백준 25757 번을 vector + find 로 문제를 풀면 시간 초과가 나게 된다

 

시간 제한이 1초이며 N 의 최대값이 100,000 -> vector find 과정에서 두번 돌게 되므로 최대 값은 무려 100억이다..

그래서 시간 초과가 나는 것!