List.indexOf() 시간 복잡도 문제

시간 복잡도 문제

https://velog.io/@adam2/Array%EC%99%80-List%EA%B7%B8%EB%A6%AC%EA%B3%A0-Java-List

List 계열 자료구조에서 indexOf() 메소드를 사용할 때 시간 복잡도가 O(n)이 발생하는 이유는, List가 기본적으로 요소들을 인덱스에 따라 순차적으로 저장하는 구조이기 때문입니다. 특정 요소를 찾아내기 위해 indexOf()는 내부적으로 리스트의 첫 번째 요소부터 시작하여 마지막 요소까지 순서대로 하나씩 비교하는 선형 탐색(Linear Search) 방식을 사용하게 되며, 이 과정에서 최악의 경우 리스트의 모든 요소 개수(n)만큼 비교 연산을 수행해야 하므로 데이터의 크기가 커질수록 검색 시간이 비례하여 늘어나 시간 복잡도가 O(n)이 됩니다.

 

리스트의 크기가 커져서 시간 복잡도가 증가하면 어떻게 하면 될까요??

 

1. HashMap을 활용하여 데이터와 인덱스 매핑

값을 Key로, 해당 데이터의 현재 인덱스(위치)를 Value로 저장하는 HashMap을 별도로 관리하는 방법입니다.

 

사용 방법

import java.util.*;

public class Example {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>(Arrays.asList("banana"));
        for(int i=0; i < 10000000; i++){
            list.add(i+"");
        }


        // 1. 매핑을 위한 HashMap 생성
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < list.size(); i++) {
            if (!map.containsKey(list.get(i))) {
                map.put(list.get(i), i);
            }
        }

        String searchElement = "banana"; // 찾고 싶은 요소

        // indexOf() 사용
        long startTimeList = System.nanoTime();
        int indexUsingList = list.indexOf(searchElement);
        long endTimeList = System.nanoTime();
        System.out.println("indexOf()로 '" + searchElement + "' 찾은 인덱스: " + indexUsingList + " (소요 시간: " + (endTimeList - startTimeList) + " ns)");

        // 2. HashMap 사용
        long startTimeMap = System.nanoTime();
        Integer indexUsingMap = map.get(searchElement);
        long endTimeMap = System.nanoTime();

        if (indexUsingMap != null) {
            System.out.println("HashMap으로 '" + searchElement + "' 찾은 인덱스: " + indexUsingMap + " (소요 시간: " + (endTimeMap - startTimeMap) + " ns)");
        } else {
            System.out.println("HashMap에 '" + searchElement + "'가 없습니다.");
        }

    }
}

1. 원본 리스트(또는 배열)를 기반으로 HashMap<원본 자료형, Integer> 형태의 맵을 생성합니다. 리스트를 한 번 순회하면서 각 요소와 그 인덱스를 맵에 저장합니다.

 

2. 이후 특정 요소의 인덱스를 찾고 싶을 때는 indexOf() 대신 HashMap.get() 메소드를 사용합니다. - get() 메소드를 사용하기 때문에 특정 요스를 찾을 때 시간 복잡도는 O(1)이 발생합니다.

 

3. 원본 리스트의 요소 위치가 변경될 경우 (추가, 삭제, 순서 변경 등), HashMap에 저장된 인덱스 정보도 반드시 함께 업데이트해주어야 합니다.

 

장점: HashMap의 get() 연산은 평균적으로 O(1)의 시간 복잡도를 가지므로, 특정 요소의 인덱스를 매우 빠르게 찾을 수 있습니다. 검색이 빈번하게 발생하는 상황에서 큰 성능 향상을 가져옵니다.

 

단점: HashMap을 추가로 유지해야 하므로 메모리 사용량이 증가합니다. 원본 리스트가 자주 변경된다면 HashMap을 업데이트하는 데 추가적인 관리 오버헤드가 발생합니다. 

 

 

2. 정렬 상태에서 이진 탐색(Binary Search) 사용

리스트의 데이터를 정렬 후 이진 탐색 알고리즘을 사용하는 방법입니다.

 

방법
1. 리스트의 데이터를 정렬합니다. (정렬은 O(n log n) 시간이 소요)

Collections.sort()나 Arrays.sort() 등을 사용할 수 있습니다.

 

2. Collections.binarySearch() 메소드를 사용합니다.

 

장점: 정렬이 완료된 후 검색 작업은 O(log n)의 시간 복잡도를 가지므로, indexOf()의 O(n)보다 훨씬 빠릅니다. 특히 검색 작업이 정렬 작업보다 훨씬 자주 일어난다면 유리합니다.

 

단점: 데이터를 사용하기 전에 반드시 정렬해야 합니다. 정렬이 필요없는 문제가 발생할 수 있으며, 동일한 값이 여러 개 있을 경우 binarySearch는 여러 중복 값 중 하나의 인덱스만 반환하며, 그 인덱스가 항상 첫 번째 또는 마지막 등장 위치라고 보장할 수 없습니다. 모든 중복 값을 찾으려면 추가적인 탐색이 필요합니다.

 

 

정리

HashMap 활용

• 리스트의 요소가 자주 변경되더라도 특정 요소의 인덱스를 즉시 O(1)에 찾아야 할 때 유리합니다. (단, 변경 시 맵 생성, 변경, 제거 리소스가 추가적으로 필요)
• 데이터에 중복이 많고 각 중복 값의 위치를 빠르게 찾아야 할 때, Map<ElementType, List<Integer>> 형태로 응용하여 사용할 수 있습니다.

이진 탐색 활용

• 리스트의 데이터가 변경되지 않거나 아주 가끔 변경되며, 검색 작업이 빈번하게 일어날 때 매우 효율적입니다. (정렬 시 리소스 발생)
• 리스트의 순서 자체가 중요하며 정렬 상태를 유지하는 것이 자연스러운 경우에 적합합니다.