JAVA 알고리즘 코딩테스트 자료구조 정리 (DAT / HashMap / ArrayList / ArrayDeque / TreeMap / PriorityQueue)

DAT / HashMap / ArrayList / ArrayDeque / TreeMap / PriorityQueue 는 각각 언제 최대 성능을 발휘할까? 

언제 써야 될까?

 

(결론) 상황에 따라 적절한 자료구조를 선택해야 하는데, DAT를 쓸 수 있는 조건이면 무조건 DAT를 쓰는것이 좋다. 가장 빠르다. 

(추가) JAVA에서는 String이 길어지면 속도가 많이 느려진다고 함. String을 key로 쓰는 경우 주의해아하며, 가급적 unique한 숫자로 바꾸는 것이 유리함. 

 

 

구분			Big O 시간복잡도
자료구조	주로 사용되는 문제 유형	주요 특징 및 사용 이유	삽입	삭제	탐색
DAT (Direct Address Table)	알파벳 빈도수 계산, 숫자 출현 여부 등 범위가 작은 경우의 빈도 체크	인덱스를 직접 접근하는 방식으로 속도가 매우 빠름. 범위가 제한적일 때 효율적.	O(1)	O(1)	O(1)
HashMap	문자열 빈도 체크, 키-값 저장 및 조회 문제, 중복 체크, 방문 여부 체크 등	키 기반의 빠른 탐색 및 저장이 가능. 대부분의 상황에서 빠른 성능을 제공	O(1)	O(1)	O(1)
ArrayList	순서가 있는 데이터 저장 및 접근, 단순 데이터 저장 및 순회 문제	인덱스로 접근 가능하며 데이터가 많지 않거나 삽입/삭제가 적은 경우 적합. 순회가 빈번한 경우 유리.	O(1) (맨 뒤 추가) O(n) (중간 추가)	O(n)	O(1) (인덱스 접근) O(n) (검색)
ArrayDeque	BFS(너비 우선 탐색), 슬라이딩 윈도우, 큐/스택 응용 문제	양쪽 끝에서 삽입/삭제 연산이 빠름. 큐와 스택 모두 가능. BFS 구현 시 가장 적합.	O(1)	O(1)	O(n) (검색)
TreeMap	키의 정렬이 필수적인 문제, 범위 검색, 정렬된 데이터 관리 문제	키가 자동으로 정렬되어 저장됨. 정렬된 데이터에 대한 접근이 필요할 때 가장 유용함.	O(log N)	O(log N)	O(log N)
PriorityQueue	최소/최대값을 빠르게 꺼내는 문제, 다익스트라 알고리즘, 힙 정렬, 그리디 알고리즘 문제	항상 가장 우선순위가 높은 값 (최소값/최대값)을 빠르게 접근 가능. 우선순위 큐 문제에서 필수적.	O(log N)	O(log N)	O(1) (peek) O(n) (검색)