코딩테스트를 보다보면 주로 1초(10^8)안에 풀어야 하는 것들이 많이 나와서 좀 더 빠른 알고리즘을 사용하기 위해선 정리가 필요해보였다.
List
| add | remove | get | contains | 자료 구조 | |
|---|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(1) | O(n) | Array |
| LinkedList | O(1) | O(1) | O(n) | O(n) | Linked List |
Set
| add | contains | next | 자료 구조 | |
|---|---|---|---|---|
| HashSet | O(1) | O(1) | O(h/n) | Hash Table |
| LinkedHashSet | O(1) | O(1) | O(1) | Hash Table + Linked List |
| EnumSet | O(1) | O(1) | O(1) | Bit Vector |
| TreeSet | O(logn) | O(logn) | O(logn) | Red-black tree |
Queue
offer() : 큐에 요소를 추가하고 반환하는 잘못된 요소를 추가 할 수없는 경우(큐가 가득 찬 경우)에 특정 예외를 throw 하지 않는다.
peek() : 큐의 처음에 있는 원소를 삭제하지 않고 가져온다. 큐가 비어있으면 null을 반환
poll() : 큐의 처음에 있는 원소를 가져온다. 큐에 원소가 없으면 null을 반환
| offer | peek | poll | size | 자료 구조 | |
|---|---|---|---|---|---|
| PriorityQueue | O(logn) | O(1) | O(logn) | O(1) | Priority Heap |
| LinkedList | O(1) | O(1) | O(1) | O(1) | Array |
| ArrayDequeue | O(1) | O(1) | O(1) | O(1) | Linked List |
Map
| get | containsKey | next | 자료 구조 | |
|---|---|---|---|---|
| HashMap | O(1) | O(1) | O(h/n) | Hash Table |
| LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List |
| EnumMap | O(1) | O(1) | O(1) | Array |
| TreeMap | O(logn) | O(logn) | O(logn) | Red-black tree |
🐻❄️
map의 value를 기반으로 탐색은 시간복잡도가 어떻게 되나요 ? 그부분도 있으면 좋을 거 같아요
잘했어요