코딩테스트 필수 자료구조

파이썬 VS 자바 

1. 배열 (시간 복잡도) => O(1) 입력값의 크기와 무관하게 일정한 속도, O(c) => 상수 시간만큼의 복잡도

언어 구분	파이썬	자바
정의	다양한 데이터 타입의 원소들이 순서대로 저장된 선형 자료 구조	동일한 데이터 타입의 원소들이 순서대로 저장된 선형 자료 구조 (Primitive / Wrapper)
선언	list = []	int [] arr = new int[]; ArrayList<Integer> aList = new ArrayList<>();
추가	list.append(값) O(1)	arr[idx] = 값; aList.add(값); O(n) : 배열이 꽉찬 경우 확장 및 복사
삭제	list.pop(idx) O(n) list.pop() 맨 뒤의 원소 삭제 O(1)	arr[idx] = 0; aList.remove(idx or obj) O(n)
접근	list[idx] O(1)	arr[idx]; arr.get(idx); O(1)
크기 확인	len(list) O(1)	arr.length aList.size(); O(1)
존재 여부	값 in list (true or false) O(n)	for(int i : arr) {System.out.println();} O(n) aList.contains(값);  O(n)

2. 해시테이블 (시간 복잡도)

언어 구분	파이썬	자바
정의	키와 값으로 이루어진 데이터를 저장하는 자료구조
선언	dt = {} or dt = dict()	HashMap<String, String> map = new HashMap<>();
추가	dt[키] = 값 O(c)	map.put(키, 값) O(n) 자바8미만 / O(logN) 자바8이상
삭제	del dt[키] O(c)	map.remove(키); O(n) 자바8미만 / O(logN) 자바8이상
접근	dt[키] O(c)	map.get(키); O(n) 자바8미만 / O(logN) 자바8이상
크기 확인	len(dt) O(1)	map.size(); O(1)
존재 여부	키 in dt (true or false) O(c)	map.containsKey(키); O(n) 자바8미만 / O(logN) 자바8이상

3.셋 (시간 복잡도)

언어 구분	파이썬(해시테이블 기반)	자바 (HashSet{정렬x} or TreeSet{정렬o})
정의	중복되지 않는 요소들의 모임
선언	s = set()	HashSet<String> set = new HashSet<>(); HashMap으로 구현
추가	s.add(값) O(c)	set.add(값); O(n)
삭제	s.remove(값) O(c) s.pop(), {임의의 값 삭제}  O(1)	set.remove(값); O(n)
크기 확인	len(s) O(1)	set.size(); O(1)
존재 여부	값 in s O(c)	set.contains(값); O(n) set1.containsAll(set2); 부분집합 여부 O(n*m)
합집합	s1 | s2 or s1.union(s2) O(len(s1) + len(s2))	set1.addAll(set2); O(n*m)
교집합	s1 & s2 or s2.intersection(s2) O(c*n) : c는 상수, n은 더 작은 셋의 크기	set1.retainAll(set2); O(n*m)
차집합	s1-s2 or s1.difference(s2) O(c*n) : c는 상수, n은 s1의 크기	set1.removeAll(set2); O(n*m)

4. 스택

언어 구분	파이썬 (deque lib import)	자바 (Stack Collection) 배열이나 연결리스트로 구현
정의	후입 선출(LIFO : Last In First Out) 구조의 선형 자료 구조
선언	from collections import deque stack = deque()	Stack<String> stack = new Stack<>();
추가	stack.append(값) O(1)	stack.push("a"); O(1)
삭제	stack.pop() O(1)	stack.pop(); O(1)
접근	stack[-1] O(1)	stack.peek(); O(1)
크기 확인	len(stack)  O(1)	stack.size() O(1)
empty	not stack OR  len(stack) == 0 O(1) ex ) if not stack : OR if stack:	stack.isEmpty(); O(1)

5.큐 

언어 구분	파이썬	자바
정의	선입선출(FIFO : First In First Out) 구조의 선형 자료 구조
선언	from collections import deque q = deque()	Queue<String> queue = new LinkedList<>();
추가	q.append(값) O(1)	queue.add("A"); O(1)
삭제	q.popleft() O(1)	queue.poll() O(1) queue.remove(); O(1)
접근	q[0] O(1)	queue.peek(); O(1)
크기 확인	len(q) O(1)	queue.size() O(1)
존재 여부	값 in q O(n)	queue.contains("A"); O(n)

6. 힙

언어 구분	파이썬	자바
정의	완전 이진트리의 일종으로, 우선순위가 높은 원소를 빠르게 접근 가능한 자료구조
선언	from collections import PriorityQueue pq = PriorityQueue()	PriorityQueue<Integer> minHeap = new PriorityQueue<>(); PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
추가	pq.put(값) 최소힙 O(logN) pq.put([-값,값]) 최대힙 O(logN) 넣으면서 우선순위에 맞게 정렬됨	minHeap.add(값); O(logN)
삭제	값 = pq.get() O(logN) 최상위 원소 삭제	minHeap.poll(); O(logN) minHeap.remove(); O(logN) minHeap.remove(값); O(N)
접근	값 = pq.queue[0] O(1) 최상위 원소 확인 (pq 내부 queue 리스트)	minHeap.peek(); O(1)
크기 확인	len(pq.queue) O(1)	minHeap.size(); O(1)
존재 여부	pq.empty() OR pq.queue O(1)	minHeap.isEmpty(); O(1)

파이썬에서는 최소힙만 보장되고 최대힙이 구현되어 있지 않다. 이때, 값이 클수록 앞에 음수 부호를 붙이면 가장 작은 수가 된다. 최소힙은 값이 작을수록 우선순위가 높아지므로 -값을 넣게 되면 최대힙이 보장된다.