[Coding Test] 자료구조 3

Do it! 알고리즘 코딩테스트 with JAVA
인프런 로드맵 보기

---

맵 (Map)

맵이란?

Key와 Value를 하나의 쌍으로 묶어서 저장하는 Key-Value 형태의 자료구조.
Key를 통해 Value에 빠르게 접근할 수 있다.

주요 구현체 및 특징

• HashMap: 가장 일반적으로 사용되는 Map. **O(1)**의 평균 시간 복잡도로 데이터를 삽입, 삭제, 조회할 수 있어 매우 빠르다.
• TreeMap: Key를 기준으로 자동 정렬되는 Map. 정렬된 순서가 필요할 때 유용하며, 시간 복잡도는 **O(log N)**이다.
• LinkedHashMap: 데이터가 삽입된 순서를 기억하는 Map. 입력된 순서대로 순회해야 할 때 사용한다.

주요 메서드 (HashMap 기준)

• put(key, value): Key-Value 쌍을 맵에 추가
• get(key): 주어진 Key에 해당하는 Value를 반환
• containsKey(key): 특정 Key가 맵에 있는지 확인
• remove(key): 특정 Key에 해당하는 데이터를 삭제

예시

// 특정 문자의 개수 세기

String str = "hello world";
HashMap<Character, Integer> charCountMap = new HashMap<>();

for (char c : str.toCharArray()) {
    // getOrDefault: key가 있으면 value를, 없으면 defaultValue(0)를 반환
    charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
}

System.out.println(charCountMap.get('l')); // 출력: 3

---

셋 (Set)

셋이란?

중복된 요소를 허용하지 않는 데이터의 집합을 다루는 자료구조. 데이터의 존재 여부를 확인할 때 매우 유용하다.

주요 구현체 및 특징

• HashSet: 가장 일반적으로 사용되는 Set. **O(1)**의 평균 시간 복잡도로 데이터를 삽입, 삭제, 조회할 수 있다. (순서 보장 X)
• TreeSet: 데이터가 자동 정렬되는 Set. 시간 복잡도는 **O(log N)**이다.

주요 메서드 (HashSet 기준)

• add(element): 요소를 추가 (이미 존재하면 false 반환)
• contains(element): 특정 요소가 포함되어 있는지 확인
• remove(element): 특정 요소를 삭제
• size(): 요소의 개수를 반환

예시

// 중복 없는 숫자 집합 만들기
HashSet<Integer> numberSet = new HashSet<>();
numberSet.add(1);
numberSet.add(2);
numberSet.add(1); // 중복된 1은 추가되지 않음

System.out.println(numberSet.size()); // 출력: 2
System.out.println(numberSet.contains(1)); // 출력: true

---

덱 (Deque)

덱(Deque)이란?

양쪽 끝에서 데이터를 삽입하고 삭제할 수 있는 ‘Double-Ended Queue’의 줄임말이다. 스택과 큐의 기능을 모두 가지고 있어 활용도가 높다.

덱의 특징

• 자바에서 스택을 구현할 때는 Stack 클래스보다 스레드 동기화 오버헤드가 없는 ArrayDeque를 사용하는 것이 성능상 권장된다.
• 큐 역시 LinkedList보다 ArrayDeque가 더 효율적이다.

예시

// ArrayDeque는 Deque 인터페이스의 구현체
Deque<Integer> deque = new ArrayDeque<>();

// 스택처럼 사용 (LIFO)
deque.push(1); // addFirst와 동일
deque.push(2);
System.out.println(deque.pop()); // removeFirst와 동일, 출력: 2

// 큐처럼 사용 (FIFO)
deque.offer(3); // offerLast와 동일
deque.offer(4);
System.out.println(deque.poll()); // pollFirst와 동일, 출력: 1

---