효율적인 코딩 테스트를 위한 Java 자료구조 선택 가이드

자료구조는 입력 데이터를 저장하고 연산을 하기 위해 사용됩니다

따라서 필요한 연산에 알맞은 자료구조의 선택은 효율적인 문제풀이에 중요한 요소입니다

Java에서 기본적으로 제공하는 대표적인 자료구조에 대해서 알아봅시다

 

1. ArrayList
   • 특징
     • 인덱스로 빠른 접근 가능
     • 크기가 동적으로 조절(O(n))
   • 시간 복잡도
     • 조회 : O(1)
     • 삽입/삭제(끝) : O(1)
     • 삽입/삭제(중간) : O(n)
     • 정렬 : O(nlogn)
   • 사용 예시
     • 인덱스를 통한 빠른 접근이 필요한 경우
     • 정렬된 데이터에서 이진 검색 수행 시
     • 동적으로 크기가 변하는 배열이 필요한 경우
2. LinkedList
   • 특징
     • 삽입, 삭제가 빠름
     • 메모리 사용이 큼
     • 인덱스로 접근 시 성능이 떨어
   • 시간 복잡도
     • 조회(처음/끝) : O(1)
     • 삽입/삭제(처음/끝) : O(1)
     • 삽입/삭제(중간) : O(n)
     • 정렬 : O(nlogn)
   • 사용 예시
     • 큐 구현
     • 캐시 구현, LRU(Least Recently Used) 알고리즘
3. HashSet
   • 특징
     • 중복 허용하지 않음
     • 순서를 보장하지 않음
     • 해시 테이블로 검색이 빠름
   • 시간 복잡도
     • 조회 : O(1)
     • 삽입 : O(1)
     • 삭제 : O(1)
     • 해시 충돌 시 조회, 삽입, 삭제의 시간 복잡도는 O(n)
     • 중복 제거 : O(1)(자동)
   • 사용 예시
     
     • 고유한 원소 세기
     • 두 집합의 교집합, 합집합, 차집합 구하기
4. TreeSet
   • 특징
     • 중복을 허용하지 않음
     • 요소가 정렬된 상태로 유지
     • 레드-블랙 트리로 구현
   • 시간 복잡도
     • 조회 : O(logn)
     • 삽입 : O(logn)
     • 삭제 : O(logn)
     • 정렬 : 삽입, 삭제 시 자동 정렬
   • 사용 예시
     • 정렬된 상태로 범위 검색
     • 최소값/최대값 자주 조회 시
5. HashMap
   • 특징
     • 키 - 값 쌍으로 데이터 저장
     • 키는 중복 불가
     • 해시 테이블로 검색이 빠름
     • 순서를 보장하지 않음
   • 시간 복잡도
     • 조회 : O(1)
     • 삽입 : O(1)
     • 삭제 : O(1)
     • 해시 충돌 시 조회, 삽입, 삭제의 시간 복잡도는 O(n)
   • 사용 예시
     • 각 단어의 빈도 수 계산
     • 캐싱 구현
6. TreeMap
   • 특징
     • 키 - 값  쌍으로 데이터 저장
     • 키는 중복 될 수 없음
     • 키를 기준으로 정렬된 상태 유지
     • 레드 - 블랙 트리로 구현
   • 시간 복잡도
     • 조회 : O(logn)
     • 삽입 : O(logn)
     • 삭제 : O(logn)
     • 정렬 : 키를 기준으로 삽입, 삭제 시 자동 정렬
   • 사용 예시
     • 정렬된 순서로 키-값 쌍 출력
     • 특정 점수 범위의 학생 찾기
7. PriorityQueue
   • 특징
     • 삽입 : O(logn)
     • 최소/최대값 조회 : O(1)
     • 최소/최대값 삭제 : O(logn)
   • 시간 복잡도
     • 우선순위에 따라 요소 처리
     • 힙(Heat) 자료구조로 구현, 기본은 최소 
   • 사용 예시
     • 다익스트라 알고리즘
     • 우선순위가 높은 작업 먼저 처리
8. Queue
   • 특징
     • 선입선출(FIFO) 구조
     • LinkedList 혹은 ArrayDeque로 구현
   • 시간 복잡도
     • 삽입(끝) : O(1)
     • 삭제(앞) : O(1)
     • 조회(앞) : O(1)
   • 사용 예시
     • BFS(너비 우선 탐색) 구현
     • 대기열 구현
9. Stack
   • 특징
     • 후입선출(LIFO) 구조
     • ArrayDeque로 구현
   • 시간 복잡도
     • 삽입(끝) : O(1)
     • 삭제(끝) : O(1)
     • 조회(끝) : O(1)
   • 사용 예시
     • DFS(깊이 우선 탐색) 구현
     • 괄호 짝 맞추기
10. Deque
    • 특징
      • 양쪽 끝에서 삽입, 삭제가 가능
      • ArrayDeque로 구현
      • 스택과 큐의 기능을 모두 수행 가능
    • 시간 복잡도
      • 삽입(양쪽 끝) : O(1)
      • 삭제(양쪽 끝) : O(1)
      • 조회(양쪽 끝) : O(1)
    • 사용 예시
      • 양쪽 끝에서 삽입/삭제가 필요한 경우
      • 슬라이딩 윈도우 알고리즘
      • 회문 검사