코딩테스트에서 자주 사용되는 Java 자료구조 등을 정리했습니다.
컬렉션 프레임워크는 다양한 자료구조를 직접 구현하지 않고, 쉽게 사용할 수 있도록 제공해줍니다.
D. Set 인터페이스
중복 X, 순서 X
연관 메서드
| 메서드 | 설명 |
|---|
add(E e) | 요소 추가, 이미 존재하면 false 반환 |
remove(Object o) | 해당 요소 제거 |
contains(Object o) | 해당 요소가 존재하는지 확인 |
isEmpty() | 비어 있는지 확인 |
size() | 집합 크기 반환 |
clear() | 모든 요소 제거 |
iterator() | 순회용 Iterator 반환 (for-each 사용 가능) |
시간 복잡도
| 연산 | HashSet 평균 | LinkedHashSet | TreeSet |
|---|
add | O(1) | O(1) | O(log n) |
remove | O(1) | O(1) | O(log n) |
contains | O(1) | O(1) | O(log n) |
- 중복 제거 + 빠른 속도 : HashSet
- 중복 제거 + 순서 유지 : LinkedHashSet
- 중복 제거 + 정렬 : TreeSet
6. HashSet 클래스
요소의 중복을 허용하지 않고 (equals()와 hashCode()로 중복 여부 판단), 순서를 보장하지 않습니다.
가장 빠른 검색/삽입/삭제 성능을 가집니다. (평균 O(1), 최악 O(n) - hashCode() 충돌이 많이 날 때)
내부적으로 HashMap을 사용합니다.
기본 사용 예시
1
2
3
4
5
6
| Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("apple"); // 중복, 추가되지 않음
System.out.println(set); // [banana, apple] (순서 보장 X)
|
7. LinkedHashSet 클래스
HashSet과 동일하지만, 입력 순서를 유지하는 자료구조입니다.
추가된 순서 또는 가장 최근에 접근한 순서대로 접근 가능합니다.
내부적으로 HashMap와 이중 연결 리스트로 구성되어 있습니다.
기본 사용 예시
1
2
3
4
5
6
| Set<String> set = new LinkedHashSet<>();
set.add("apple");
set.add("banana");
set.add("cherry");
System.out.println(set); // [apple, banana, cherry]
|
8. TreeSet 클래스
중복을 허용하지 않고 순서를 가지지 않지만, 데이터를 정렬된 상태로 저장합니다.
기본적으로 오름차순 정렬이고, Comparable 또는 Comparator 구현으로 커스터마이징 가능합니다.
내부적으로 Red-Black Tree(이진 균형 트리)를 사용합니다.
기본 사용 예시
1
2
3
4
5
6
| Set<Integer> set = new TreeSet<>();
set.add(30);
set.add(10);
set.add(20);
System.out.println(set); // [10, 20, 30]
|
정렬 기준 커스터마이징
1
2
3
4
5
6
| Set<String> set = new TreeSet<>(Comparator.reverseOrder());
set.add("apple");
set.add("banana");
set.add("cherry");
System.out.println(set); // [cherry, banana, apple]
|
E. Map 인터페이스
key-value 쌍 저장(key 고유), 순서 X
연관 메서드
| 메서드 | 설명 |
|---|
put(K key, V value) | key-value 추가 |
putAll(Map t) | 지정된 Map의 모든 쌍 추가 |
get(Object key) | key로 value 조회 |
containsKey(Object key) | key 존재 여부 |
containsValue(Object value) | value 존재 여부 |
remove(Object key) | 해당 key 제거 |
keySet() | key 집합 반환 (Set) |
values() | 모든 value 반환 (Collection) |
entrySet() | key-value 쌍 Map.Entry타입의 객체로 저장한 Set을 반환 |
size() | 요소 개수 반환 |
clear() | 전체 요소 삭제 |
equals(Object o) | 동일한 Map인지 비교 |
isEmpty() | Map이 비어있는지 확인 |
hashCode() | 해시코드 반환 |
시간 복잡도
| 연산 | HashMap | LinkedHashMap | TreeMap |
|---|
| 삽입 | O(1) | O(1) | O(log n) |
| 검색 | O(1) | O(1) | O(log n) |
| 삭제 | O(1) | O(1) | O(log n) |
Map.Entry 인터페이스
- Map.Entry는 Map 내부에 정의된 중첩(static) 인터페이스입니다.
- 하나의 key-value 쌍을 표현합니다.
- 일반적으로 Map을 순회할 때 가장 유용한 방식입니다.
1
2
3
4
5
6
7
8
9
10
11
12
| Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.put("banana", 5);
// Entry 사용
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
}
// 빈도 기준 정렬 (내립차순)
List<Map.Entry<Integer, Integer>> sortedList = new ArrayList<>(freqMap.entrySet());
sortedList.sort((a, b) -> b.getValue() - a.getValue());
|
| 메서드 | 설명 |
|---|
K getKey() | key 반환 |
V getValue() | value 반환 |
V setValue(V value) | value 변경 (일반적으로 사용 지양) |
boolean equals(Object o) | 두 Entry가 같은지 비교 |
int hashCode() | Entry의 해시값 반환 |
9. HashMap 클래스
Hashtable을 보완한 컬렉션으로 비순서 해시 기반 맵입니다.
key는 중복 불가하고 value는 중복이 가능하며, key/value에 null이 허용됩니다.
순서를 보장하지 않습니다.
가장 일반적이고, 빠른 성능을 보입니다.
기본 사용 예시
1
2
3
4
5
6
7
8
9
| Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.put("banana", 5);
System.out.println(map.get("apple")); // 3
// key값들을 set으로 반환 및 순회
for(String key : map.keySet()) {
System.out.println(key + " => " + map.get(key));
}
|
10. LinkedHashMap 클래스
HashMap을 상속하므로 흡사하지만, Entry들이 연결 리스트를 구성하여 데이터의 순서를 보장합니다.
삽입된 순서대로 순서를 가집니다.
기본 사용 예시
1
2
3
4
5
6
7
8
| Map<String, String> lhm = new LinkedHashMap<>();
lhm.put("first", "a");
lhm.put("second", "b");
System.out.println(lhm); // {first=a, second=b}
for(Integer key : lhm.keySet()) {
System.out.println(key + " => " + lhm.get(key));
}
|
11. TreeMap 클래스
SortedMap 인터페이스를 구현하고 있어 Key 값을 기준으로 정렬됩니다.
정렬된 순서로 저장하므로 빠른 검색(특히 범위 검색)이 가능합니다.
단, 키와 값을 저장하는 동시에 정렬하므로 저장 시간이 다소 오래 걸립니다.
정렬되는 순서는 숫자 → 알파벳 대문자 → 알파벳 소문자 → 한글 순이며, 기본적으로 오름차순입니다.
key에 null은 불가능하고, TreeSet과 같은 원리입니다.
기본 사용 예시
1
2
3
4
5
6
7
8
| Map<String, Integer> tm = new TreeMap<>();
tm.put("c", 1);
tm.put("a", 2);
System.out.println(tm); // {a=2, c=1}
for(Integer key : tm.keySet()) {
System.out.println(key + " => " + tm.get(key));
}
|
참고 블로그
