JCF: Java Collections Framework

컬렉션 (Java Collections Framework, JCF)

자바 컬렉션 프레임워크(Java Collections Framework, JCF)는 데이터 구조를 효율적으로 다룰 수 있도록 자바에서 제공하는 클래스와 인터페이스의 집합이다. 이를 활용하면 데이터 저장, 검색, 수정, 삭제 등의 작업을 간편하게 수행할 수 있다.

Collection인터페이스를 상속받는 주요 자식 인터페이스(Set, List, Queue, Map)이 있으며 각 인터페이스에는 주요하게 사용되는 구조체가 있다.

인터페이스에 구조체를 넣어 사용하거나, 구조체 자체를 클래스화 시켜서 사용하면 된다.

인터페이스

JCF는 인터페이스 기반 설계를 따르며, 다음과 같은 주요 인터페이스들이 존재한다:

Collection – 모든 컬렉션의 루트 인터페이스
- List – 순서가 있는 데이터 집합, 중복 허용
- Set – 순서를 보장하지 않으며 중복을 허용하지 않음
- Queue – FIFO 구조
Map – 키-값 쌍으로 이루어진 구조 (Collection의 하위는 아님)

인터페이스 별 구현체

1. `Collection` 인터페이스

Collection은 모든 컬렉션의 기본 인터페이스로, 요소 추가, 제거, 탐색 등의 메서드를 제공한다.

2. `Set` 인터페이스

중복을 허용하지 않는 컬렉션이다.
요소들의 순서를 보장하지 않는다.
주요 구현 클래스:
- HashSet: 해시 테이블을 기반으로 하며, 순서를 보장하지 않는다.
- LinkedHashSet: 입력된 순서를 유지한다.
- TreeSet: 정렬된 순서로 저장한다.

3. `List` 인터페이스

순서가 있는 컬렉션으로, 중복 요소를 허용한다.
요소를 인덱스를 통해 접근할 수 있다.
주요 구현 클래스:
- ArrayList: 동적 배열로 구현되어 있다.
- LinkedList: 연결 리스트로 구현되어 있다.
- Vector: 동기화를 지원하며, 스택과 유사하다.
- Stack: LIFO(Last In, First Out) 구조를 제공한다.

4. `Queue` 인터페이스

FIFO(First In, First Out) 구조를 가지는 컬렉션이다.
주요 구현 클래스:
- LinkedList: 연결 리스트 기반의 큐 구현체이다.
- PriorityQueue: 우선순위에 따라 요소를 관리한다.

5. `Map` 인터페이스

키와 값의 쌍으로 이루어진 데이터를 저장하는 컬렉션이다.
키는 중복을 허용하지 않으며, 값은 중복을 허용한다.
주요 구현 클래스:
- HashMap: 해시 테이블 기반으로 데이터를 저장한다.
- LinkedHashMap: 입력된 순서를 유지한다.
- TreeMap: 키를 정렬된 순서로 저장한다.
- Hashtable: 동기화를 지원한다.

컬렉션 구조 다이어그램

graph LR Collection("Collection
JCF 관점 전체 컬렉션 구조") List("List
순서가 있는 자료 접근") Set("Set
중복없이 자료 접근") Map("Map
키와 값으로 데이터 접근") LinkedList("LinkedList
연결리스트로 구현된 리스트") Stack("Stack
스택구조로 접근") Vector("Vector
동기화 지원") ArrayList("ArrayList
동적 배열로 접근") HashSet("HashSet
동적 해시 테이블로 구현") SortedSet("SortedSet
정렬된 자료 접근 가능한 인터페이스") TreeSet("TreeSet
트리 구조로 정렬된 자료 접근") Hashtable("Hashtable
동기화 지원하는 Map 자료구조") HashMap("HashMap
동적 해시맵으로 데이터 접근") SortedMap("SortedMap
정렬된 자료로 Map 자료 접근") TreeMap("TreeMap
트리 구조로 정렬된 Map 자료 접근") Collection --> List Collection --> Set Collection --> Map List --> LinkedList List --> Stack List --> Vector List --> ArrayList Set --> HashSet Set --> SortedSet SortedSet --> TreeSet Map --> Hashtable Map --> HashMap Map --> SortedMap SortedMap --> TreeMap

Collection의 상속 구조

Java Collections Framework의 클래스와 인터페이스는 상속 관계를 통해 구조화되어 있다.

1. 기본 상속 구조

Collection은 모든 컬렉션 클래스의 상위 인터페이스이다.
List와 Set은 각각 순서와 중복 여부를 기준으로 구현된다.

graph LR Collection("Collection
JCF 관점 전체 컬렉션 구조") List("List
순서가 있는 자료 접근") Set("Set
중복없이 자료 접근") LinkedList("LinkedList
연결리스트로 구현된 리스트") Stack("Stack
스택구조로 접근") Vector("Vector
동기화 지원") ArrayList("ArrayList
동적 배열로 접근") HashSet("HashSet
동적 해시 테이블로 구현") SortedSet("SortedSet
정렬된 자료 접근 가능한 인터페이스") TreeSet("TreeSet
트리 구조로 정렬된 자료 접근") Collection --> List Collection --> Set List --> LinkedList List --> Stack List --> Vector List --> ArrayList Set --> HashSet Set --> SortedSet SortedSet --> TreeSet

2. Map 구조

Map은 Collection과 별도로 키-값 쌍 구조를 제공한다. 구현 클래스는 다양한 정렬 및 동기화 방식에 따라 분리된다.

graph LR Map("Map
키와 값으로 데이터 접근") Hashtable("Hashtable
동기화 지원하는 Map 자료구조") HashMap("HashMap
동적 해시맵으로 데이터 접근") SortedMap("SortedMap
정렬된 자료로 Map 자료 접근") TreeMap("TreeMap
트리 구조로 정렬된 Map 자료 접근") Map --> Hashtable Map --> HashMap Map --> SortedMap SortedMap --> TreeMap

유틸리티 메서드

1. `List` 인터페이스 (대표: `ArrayList`, `LinkedList`)

메서드	설명	예시
`add(E e)`	요소 추가	`list.add("apple");`
`add(int index, E e)`	특정 위치에 삽입	`list.add(1, "banana");`
`get(int index)`	인덱스로 요소 가져오기	`list.get(0);`
`set(int index, E e)`	특정 위치 값 수정	`list.set(1, "cherry");`
`remove(int index)`	인덱스로 삭제	`list.remove(2);`
`remove(Object o)`	값으로 삭제	`list.remove("apple");`
`size()`	요소 개수	`list.size();`
`contains(Object o)`	포함 여부 확인	`list.contains("apple");`
`indexOf(Object o)`	처음 등장하는 인덱스	`list.indexOf("apple");`
`isEmpty()`	비어 있는지 확인	`list.isEmpty();`
`clear()`	전체 요소 삭제	`list.clear();`

예제

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add(1, "c"); // [a, c, b]
list.set(0, "x"); // [x, c, b]
list.remove("c"); // [x, b]
System.out.println(list.get(1)); // b

2. `Set` 인터페이스 (대표: `HashSet`, `LinkedHashSet`, `TreeSet`)

메서드	설명	예시
`add(E e)`	요소 추가	`set.add("apple");`
`remove(Object o)`	요소 삭제	`set.remove("apple");`
`contains(Object o)`	포함 여부 확인	`set.contains("banana");`
`size()`	요소 개수	`set.size();`
`isEmpty()`	비어 있는지 확인	`set.isEmpty();`
`clear()`	전체 삭제	`set.clear();`
`iterator()`	반복자 반환	`for (String s : set) { ... }`

예제

Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("a"); // 중복 무시
System.out.println(set.contains("b")); // true
set.remove("a");

3. `Queue` 인터페이스 (대표: `LinkedList`, `PriorityQueue`)

메서드	설명	예시
`add(E e)`	요소 추가 (예외 발생 가능)	`queue.add("apple");`
`offer(E e)`	요소 추가 (실패 시 false 반환)	`queue.offer("apple");`
`poll()`	요소 꺼내고 제거	`queue.poll();`
`peek()`	요소 꺼내되 제거 안 함	`queue.peek();`
`remove()`	요소 꺼내고 제거 (비었으면 예외)	`queue.remove();`
`element()`	요소 조회 (비었으면 예외)	`queue.element();`

예제

Queue<String> queue = new LinkedList<>();
queue.offer("a");
queue.offer("b");
System.out.println(queue.peek()); // a
System.out.println(queue.poll()); // a (삭제됨)

4. `Map` 인터페이스 (대표: `HashMap`, `LinkedHashMap`, `TreeMap`)

메서드	설명	예시
`put(K key, V value)`	값 추가 또는 덮어쓰기	`map.put("apple", 3);`
`get(Object key)`	키로 값 조회	`map.get("apple");`
`remove(Object key)`	키로 값 삭제	`map.remove("apple");`
`containsKey(Object key)`	키 존재 여부	`map.containsKey("apple");`
`containsValue(Object value)`	값 존재 여부	`map.containsValue(3);`
`keySet()`	모든 키 반환	`for (String k : map.keySet())`
`values()`	모든 값 반환	`for (int v : map.values())`
`entrySet()`	키-값 쌍 반환	`for (Map.Entry<String, Integer> e : map.entrySet())`
`size()`	크기	`map.size();`
`isEmpty()`	비어 있는지 확인	`map.isEmpty();`
`clear()`	모두 제거	`map.clear();`

예제

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 3);
map.put("apple", 10); // 값 덮어쓰기

System.out.println(map.get("apple")); // 10

for (String key : map.keySet()) {
    System.out.println(key + " : " + map.get(key));
}

요약 정리

컬렉션	자주 쓰는 메서드 요약
`List`	`add()`, `get()`, `set()`, `remove()`, `size()`
`Set`	`add()`, `remove()`, `contains()`, `iterator()`
`Queue`	`offer()`, `poll()`, `peek()`
`Map`	`put()`, `get()`, `remove()`, `containsKey()`, `entrySet()`

Stack 사용방법

Java에서도 Stack이 존재하지만, Java Collections Framework(JCF)에서는 덜 권장되는 자료구조로 간주된다.
그래도 Stack은 명확히 존재하고 사용 가능하며 대안으로 deque를 권장한다.

1. `Stack` 클래스

java.util.Stack 클래스는 Vector를 상속한 클래스로, LIFO(Last-In-First-Out) 구조를 구현한다.

메서드	설명
`push(E item)`	스택 맨 위에 요소 추가
`pop()`	스택 맨 위 요소 꺼내고 제거
`peek()`	스택 맨 위 요소 반환 (제거 X)
`empty()`	비어 있는지 확인
`search(Object o)`	요소 위치 반환 (1부터 시작), 없으면 -1

사용 예시

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30); // [10, 20, 30]

System.out.println(stack.peek()); // 30
System.out.println(stack.pop());  // 30
System.out.println(stack.empty()); // false

2. 왜 Stack은 잘 안 쓰이나?

Stack은 JCF 안에서 있지만, 다음과 같은 이유로 권장되지 않는다:

Stack은 Vector를 상속받는데, Vector는 오래된 동기화 자료구조다.
더 가볍고 효율적인 대안인 Deque (Double-ended Queue) 사용이 추천된다.

3. 대안: `Deque` 인터페이스 (대표 구현체: `ArrayDeque`)

Deque는 양쪽에서 삽입/삭제가 가능한 자료구조지만, 한쪽만 사용하면 스택처럼 작동한다.

주요 메서드 (스택처럼 사용할 때)

메서드	설명
`push(E e)`	맨 앞에 삽입 (스택의 `push`)
`pop()`	맨 앞에서 꺼냄 (스택의 `pop`)
`peek()`	맨 앞 요소 확인 (스택의 `peek`)

예시

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3); // [3, 2, 1]

System.out.println(stack.pop()); // 3
System.out.println(stack.peek()); // 2

추가로, 큐처럼 쓰고 싶다면 queue.offer(), queue.poll()을 사용하고, 스택처럼 쓰고 싶다면 deque.push(), deque.pop()을 사용하면 된다.

어떤 인터페이스에 넣어야 하는가

자료구조	인터페이스에 넣기	스택 기능 사용 가능 여부	설명
`Stack`	`List`, `Collection`, `Iterable`	❌	스택 메서드 (`push`, `pop`)는 못 씀
`Stack`	`Stack`	⭕️	`push`, `pop`, `peek` 모두 사용 가능
`ArrayDeque`	`Deque`	⭕️	스택처럼 사용 가능. 성능도 우수

결과적으로 아래의 방식을 추천한다.

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
System.out.println(stack.pop()); // "B"

## 이터레이터

Java의 컬렉션에서도 C++ STL처럼 이터레이터(iterator) 를 지원한다. Java에서는 Iterator라는 인터페이스가 따로 정의되어 있으며, List, Set, Map 등 대부분의 JCF 컬렉션에서 이터레이터를 사용할 수 있다.

Iterator는 컬렉션의 요소를 순차적으로 접근하기 위한 객체이다.
for-each 루프(for (E e : collection))도 내부적으로는 Iterator를 사용한다.

기본 메서드

Iterator<E> iterator = collection.iterator();

메서드	설명
`hasNext()`	다음 요소가 있는지 확인
`next()`	다음 요소 반환
`remove()`	현재 요소 삭제 (한 번만 호출 가능)

예제 1: `List`에서 Iterator 사용

List<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("cherry");

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String fruit = it.next();
    System.out.println(fruit);
}

예제 2: `Set`에서 Iterator 사용

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);

Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
    int value = it.next();
    System.out.println(value);
}

예제 3: `Map`에서 Iterator 사용

Map 자체는 iterator()를 제공하지 않지만, entrySet(), keySet(), values() 에 대해 이터레이터를 사용할 수 있다.

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);

Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, Integer> entry = it.next();
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

언제 사용하는가가?

for-each로는 삭제가 불가능하지만, iterator.remove()를 사용하면 순회 중 안전하게 삭제할 수 있다.
LinkedList 등에서 노드 구조를 따라가야 할 때 직접 제어가 가능하다.
반복문을 제어해야 하거나, 복잡한 조건으로 순회할 때 유용하다.

for-each와의 관계

for (String s : list) {
    System.out.println(s);
}

이 코드는 내부적으로 Iterator를 사용하는 문법적인 축약형이다.
하지만 이 방식에서는 remove()를 사용할 수 없다. 직접 Iterator 객체를 얻어야만 요소 삭제가 가능하다.

왜 for-each는 remove호출이 안될까?

✅ 전제: `for-each`문은 내부적으로 `Iterator`를 사용한다

for (String item : list) {
    ...
}

이 문장은 내부적으로 다음과 같은 코드로 변환된다:

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    ...
}

즉, for-each는 실제로는 Iterator를 사용하는 “편의 문법(Syntax Sugar)”일 뿐이다.

✅ 그런데 왜 `remove()`는 안 되는가?

그 이유는 다음과 같다:

1. `Iterator` 객체를 직접 다룰 수 없기 때문

for-each는 컴파일러가 자동으로 만든 Iterator 객체를 숨긴다.
개발자는 그 Iterator 객체에 직접 접근할 수 없으므로, it.remove() 호출이 불가능하다.

2. `Collection.remove()`를 호출하면 `ConcurrentModificationException` 발생 가능

예를 들어, 아래 코드는 런타임 예외를 발생시킨다:

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");

for (String s : list) {
    if (s.equals("a")) {
        list.remove(s); // ❌ ConcurrentModificationException
    }
}

이유: for-each는 내부적으로 Iterator를 사용하지만, remove()는 ArrayList 자체의 구조를 변경하기 때문에 Iterator가 감지하고 예외를 던진다.
리스트가 순회하면서 데이터를 삭제를 하는 도중에 인덱스가 바뀌게 되면서 현재 가리키고 있는 인덱스가 리스트의 크기보다 커지면 발생
컬렉션에는 엘리먼트가 추가되거나 삭제되면 modCount 변수를 수정하는 동작이 추가되어있다. Iterator클래스의 next()메서드에는 순회가 시작될때 컬렛견의 modCount와 현재 modCount를 비교한다. 이때 두 값이 달라지면 ConcurrentModificationException이 발생한다.
비슷하게 두 스레드가 동시에 컬렉션에 접근하는 과정에서도 발생할 수 있다.
즉 Iterator가 컬렉션의변동을 감지하기 떄문에 생기는 문제
이를 해결하기 위해서는 컬렉션을 통해 삭제하지말고 iterator를 통해 수정하라
ConcurrentModificationException 이 발생하지 않아도, 낮은 index에서 높은 index로 탐색하면서 요소를 삭제하면 탐색에서 제외되는 아이템이 발생할 수 도 있다.

✅ 해결 방법: `Iterator`를 직접 사용하여 `remove()` 호출

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("a")) {
        it.remove(); // ✅ 안전하게 삭제 가능
    }
}

Iterator는 내부 상태를 알기 때문에 현재 순회 중인 요소를 안전하게 제거할 수 있다.

✅ 핵심 요약

구분	가능 여부	이유
`for-each` 안에서 `collection.remove()`	❌	ConcurrentModificationException 발생 가능
`for-each` 안에서 `iterator.remove()`	❌	`Iterator` 객체에 접근 불가
`Iterator` 직접 사용하여 `remove()`	⭕️	안전하게 순회 및 삭제 가능

정렬

사용자 정의하는 방법은

객체의 경우 Comparable의 구현체로 만들어 compareTo() 메서드를 오버라이딩하거나

sort 함수에 Comparator<> 객체를 인자로 넣으면서 public int compare을 오버라이딩하거나

1. 기본 정렬 (Natural Order)

List<Integer> list = new ArrayList<>();
list.add(3);
list.add(1);
list.add(2);

Collections.sort(list); // 또는 list.sort(null);

System.out.println(list); // [1, 2, 3]

작동 원리

Comparable 인터페이스를 구현한 클래스들은 기본 정렬이 가능하다.
예: Integer, String, Double 등은 Comparable을 구현하고 있다.

public interface Comparable<T> {
    int compareTo(T o);
}

compareTo() 메서드는 다음을 반환한다:
- 음수 → 현재 객체가 앞에
- 0 → 같은 위치
- 양수 → 현재 객체가 뒤에

2-1. 사용자 정의 정렬 (`Comparator` 사용)

Collections.sort(List list, Comparator<? super T> c)

Collections.sort(list, Comparator.comparing(String::length));

List.sort(Comparator<? super T> c)

list.sort(Comparator.comparing(String::length));

Comparator란?

Comparable은 클래스 내부에 정렬 기준을 넣는 방식이고,
Comparator는 외부에서 정렬 기준을 “추가로” 주는 방식이다.

public interface Comparator<T> {
    int compare(T o1, T o2);
}

예시: 문자열 길이 기준 정렬

List<String> list = Arrays.asList("apple", "kiwi", "banana");

list.sort(new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return Integer.compare(s1.length(), s2.length());
    }
});
System.out.println(list); // [kiwi, apple, banana]

2-2. 사용자 정의 정렬 (`Comparable` 사용)

Comparable을 구현하는 것은 객체 스스로 정렬 기준을 가지도록 만드는 방법이다. 이를 통해 Collections.sort() 또는 List.sort(null) 등을 사용할 때 별도의 정렬 기준을 주지 않아도 된다.

정렬하고자 하는 클래스에 implements Comparable<T> 선언
compareTo(T o) 메서드를 오버라이딩하여 정렬 기준을 정의
Collections.sort() 또는 List.sort(null)을 사용하면 자동 정렬됨

class Person implements Comparable<Person> {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        // 1단계: 나이 오름차순 비교
        if (this.age < other.age) return -1;
        if (this.age > other.age) return 1;

        // 2단계: 나이가 같을 경우 이름 사전순 비교
        int minLength = Math.min(this.name.length(), other.name.length());
        for (int i = 0; i < minLength; i++) {
            char c1 = this.name.charAt(i);
            char c2 = other.name.charAt(i);
            if (c1 < c2) return -1;
            if (c1 > c2) return 1;
        }

        // 3단계: 길이가 다를 경우 더 짧은 문자열이 먼저
        if (this.name.length() < other.name.length()) return -1;
        if (this.name.length() > other.name.length()) return 1;

        return 0; // 완전히 동일
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

 List<Person> people = new ArrayList<>();
Collections.sort(people);

3. 람다를 사용한 정렬

Java 8부터는 Comparator를 람다식으로 간단히 쓸 수 있다.

list.sort((s1, s2) -> Integer.compare(s1.length(), s2.length()));

또는 Comparator.comparing() 사용:

list.sort(Comparator.comparing(String::length));

4. 역순 정렬

기본 타입 역순

List<Integer> nums = Arrays.asList(3, 1, 2);
nums.sort(Comparator.reverseOrder());
System.out.println(nums); // [3, 2, 1]

사용자 기준 역순

list.sort(Comparator.comparing(String::length).reversed());

5. 객체 리스트 정렬 (클래스 정렬)

예시 클래스

class Student {
    String name;
    int score;

    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

방법 1: `Comparable` 구현

class Student implements Comparable<Student> {
    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.score, other.score); // score 기준 정렬
    }
}

Collections.sort(studentList); // 또는 studentList.sort(null)

방법 2: `Comparator` 이용 (동적 정렬 가능)

studentList.sort(Comparator.comparing(student -> student.score));

이름 역순 정렬:

studentList.sort(Comparator.comparing((Student s) -> s.name).reversed());

6. `Map` 정렬

Map은 기본적으로 순서를 보장하지 않지만, 다음과 같은 방법으로 정렬 가능하다.

Key 기준 정렬

Map<String, Integer> map = new HashMap<>();
map.put("b", 2);
map.put("a", 1);

Map<String, Integer> treeMap = new TreeMap<>(map); // Key 기준 자동 정렬
System.out.println(treeMap); // {a=1, b=2}

Value 기준 정렬 (Stream 이용)

map.entrySet().stream()
    .sorted(Map.Entry.comparingByValue())
    .forEach(System.out::println);

7. 정렬 알고리즘 (내부 동작)

Collections.sort()는 내부적으로 TimSort 알고리즘 사용
TimSort는 MergeSort와 InsertionSort의 하이브리드
안정 정렬(Stable Sort) → 같은 값이면 원래 순서 유지

8. 정렬 관련 주요 메서드 요약

메서드	설명
`Collections.sort(list)`	기본 정렬 (Comparable 사용)
`list.sort(Comparator)`	Comparator 기반 정렬
`Comparator.comparing()`	비교 기준 정의
`Comparator.reverseOrder()`	역순 정렬
`Map.Entry.comparingByValue()`	Map 값 기준 정렬
`TreeMap`, `TreeSet`	정렬된 컬렉션 구현체

주의사항

null 요소가 있으면 NullPointerException 발생할 수 있음
compareTo나 compare의 리턴 값이 일관되지 않으면 정렬이 실패하거나 예외 발생
정렬된 컬렉션(TreeMap, TreeSet)은 삽입 시 자동 정렬이 일어남

Binary Search

C++ STL에는 <algorithm> 헤더를 통해 binary_search, lower_bound, upper_bound 같은 정렬 기반 탐색 함수들이 제공된다.
Java Collection Framework(JCF)에서도 비슷한 기능을 제공하지만, C++과는 방식이나 위치가 조금 다르다.
JCF에서는 Collections 클래스 또는 Arrays 클래스의 binarySearch() 메서드를 통해 사용한다.

Java에서의 이진 탐색: `Collections.binarySearch()`, `Arrays.binarySearch()`

대상	사용 클래스	메서드
`List<T>`	`Collections`	`binarySearch(List<T> list, T key)`
배열 `T[]`	`Arrays`	`binarySearch(T[] array, T key)`

예시 1: `List`에 이진 탐색

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(10, 20, 30, 40, 50);
        Collections.sort(list); // binarySearch는 정렬된 리스트에서만 가능

        int index = Collections.binarySearch(list, 30);
        System.out.println(index); // 2
    }
}

반환값은 해당 원소의 인덱스
없다면 (-삽입위치 - 1) 형태의 음수 값

예시 2: 배열에 이진 탐색

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 10, 15, 20};
        Arrays.sort(arr); // 생략 가능

        int idx = Arrays.binarySearch(arr, 15);
        System.out.println(idx); // 2
    }
}

lower_bound, upper_bound는 없나?

Java에는 C++의 lower_bound, upper_bound와 정확히 동일한 함수는 없다.
하지만 유사한 기능은 TreeSet, TreeMap 등에서 제공한다.

예시: `TreeSet`

TreeSet<Integer> set = new TreeSet<>();
set.add(10);
set.add(20);
set.add(30);

System.out.println(set.ceiling(15)); // lower_bound (≥) → 20
System.out.println(set.floor(25));   // upper_bound (<) → 20
System.out.println(set.higher(20));  // > → 30
System.out.println(set.lower(20));   // < → 10

메서드	의미
`ceiling(x)`	x 이상인 가장 작은 값 (lower_bound)
`floor(x)`	x 이하인 가장 큰 값
`higher(x)`	x 초과인 가장 작은 값 (strict upper_bound)
`lower(x)`	x 미만인 가장 큰 값

그 밖의 유용한 함수들

1. `Collections` 클래스의 유틸리티 메서드

java.util.Collections는 리스트나 컬렉션을 다룰 때 자주 사용된다.

함수	설명
`Collections.sort(list)`	리스트 오름차순 정렬 (Comparable 기반)
`Collections.sort(list, comparator)`	리스트를 사용자 정의 기준으로 정렬
`Collections.reverse(list)`	리스트를 반대로 뒤집음
`Collections.shuffle(list)`	리스트 요소를 무작위로 섞음
`Collections.max(list)`	최댓값 반환 (Comparable 기준)
`Collections.min(list)`	최솟값 반환
`Collections.binarySearch(list, key)`	이진 탐색 (정렬되어 있어야 함)
`Collections.fill(list, val)`	리스트를 모두 특정 값으로 채움

2. `List` 관련 함수 (특히 `ArrayList`, `LinkedList`)

메서드	설명
`add(val)`	값 추가
`add(index, val)`	특정 위치에 삽입
`remove(index)` or `remove(val)`	인덱스 또는 값 제거
`get(index)`	인덱스로 접근
`set(index, val)`	값 변경
`contains(val)`	포함 여부 확인
`indexOf(val)`	첫 등장 위치
`lastIndexOf(val)`	마지막 등장 위치
`subList(from, to)`	리스트 부분 추출 (슬라이싱)

3. `Set` 관련 (`HashSet`, `TreeSet` 등)

메서드	설명
`add(val)`	값 추가 (중복 X)
`remove(val)`	값 제거
`contains(val)`	포함 여부 확인
`size()`	크기 반환
`isEmpty()`	비었는지 확인
`clear()`	초기화

TreeSet만의 특징

정렬된 상태 유지
floor(x), ceiling(x), lower(x), higher(x) 등 범위 탐색 가능 (C++의 lower_bound, upper_bound 느낌)

4. `Map` 관련 (`HashMap`, `TreeMap` 등)

메서드	설명
`put(key, val)`	값 삽입
`get(key)`	값 가져오기
`containsKey(k)` / `containsValue(v)`	키/값 존재 확인
`remove(key)`	삭제
`keySet()`	모든 키 조회
`values()`	모든 값 조회
`entrySet()`	key-value 쌍 반복 가능 (`Map.Entry`)

5. `PriorityQueue` (우선순위 큐)

메서드	설명
`add(val)` / `offer(val)`	값 추가
`poll()`	우선순위 가장 높은 값 제거 및 반환
`peek()`	제거하지 않고 최상위 값 확인
`isEmpty()`	비었는지 확인
`size()`	크기 확인

최소힙이 기본 (오름차순 정렬)
Comparator를 사용해 최대힙으로 변경 가능

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

6. `Deque` (`ArrayDeque`) → 스택/큐 양쪽 가능

메서드	설명
`addFirst()`, `addLast()`	양쪽 삽입
`removeFirst()`, `removeLast()`	양쪽 제거
`peekFirst()`, `peekLast()`	양쪽 조회
`isEmpty()`, `size()`	상태 확인

→ BFS, 슬라이딩 윈도우, 투 포인터 등에 매우 유용

7. `Arrays` 클래스 (정렬/탐색/변환)

함수	설명
`Arrays.sort(arr)`	배열 정렬
`Arrays.binarySearch(arr, val)`	배열 이진 탐색
`Arrays.copyOf(arr, newSize)`	크기 변경 복사
`Arrays.equals(arr1, arr2)`	배열 비교
`Arrays.fill(arr, val)`	배열 전체 초기화
`Arrays.toString(arr)`	배열 출력용 문자열 생성

문제 유형	추천 자료구조/메서드
정렬 후 이진 탐색	`Collections.sort()` + `Collections.binarySearch()`
중복 제거 + 정렬된 삽입	`TreeSet`
빈도 카운팅	`HashMap<K, Integer>`
Sliding Window	`Deque`
우선순위 작업 (최소/최대값 추적)	`PriorityQueue`
DFS/BFS	`Stack`, `Queue`, `Deque`
트라이, 라딕스 트리 등 구현 시	`Map<Character, Node>`

참고

Java Collections Framework 공식 문서: Oracle Java Documentation
Wikipedia: Java Collections Framework

컬렉션 (Java Collections Framework, JCF)

인터페이스

인터페이스 별 구현체

1. Collection 인터페이스

2. Set 인터페이스

3. List 인터페이스

4. Queue 인터페이스

5. Map 인터페이스