[코딩테스트] 자료구조 - Map & Set

1. Set

Set은 중복 없는 데이터를 저장하는 자료구조다

• 중복 자동 제거
• 순서는 보장하지 않음
• O(1) 시간복잡도
• 가장 빠름

HashSet<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(1);  // 중복, 추가 안됨
System.out.println(set.size());  // 2

// 존재 여부 확인
if (set.contains(1)) { }  // O(1)

// 삭제
set.remove(1);  // O(1)

1-1) TreeSet

• 자동 정렬(오름차순)
• O(log n)
• 범위 검색이 필요할 때 사용

TreeSet<Integer> set = new TreeSet<>();
set.add(5);
set.add(1);
set.add(3);
// 저장 순서: [1, 3, 5] 자동 정렬됨

// 유용한 메서드들
set.first();     // 1 (최솟값)
set.last();      // 5 (최댓값)
set.lower(3);    // 1 (3보다 작은 수 중 최대)
set.higher(3);   // 5 (3보다 큰 수 중 최소)
set.floor(4);    // 3 (4 이하인 수 중 최대)
set.ceiling(2);  // 3 (2 이상인 수 중 최소)


// 역순 정렬
TreeSet<Integer> set2 = new TreeSet<>(Collections.reverseOrder());

2. Map

• Key-value 형태로 쌍을 저장함
• 순서를 보장하지 않음

HashMap<String, Integer> map = new HashMap<>();

// 추가/수정
map.put("apple", 1);
map.put("banana", 2);
map.put("apple", 3);  // 덮어쓰기, apple의 값이 3으로 변경

// 조회
map.get("apple");  // 3
map.get("grape");  // null (없으면 null 반환)
map.getOrDefault("grape", 0);  // 0 (없으면 기본값 반환)

// 존재 여부
map.containsKey("apple");    // true
map.containsValue(2);        // true

// 삭제
map.remove("apple");

// 크기
map.size();

2-1) TreeMap

• Key 기준으로 자동정렬

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "three");
map.put(1, "one");
map.put(2, "two");
// Key 순서: 1, 2, 3 (자동 정렬)