리스트에서 중복 요소를 확인하는 방법

1. 이중 반복문 사용하기

가장 기본적인 방법은 리스트의 모든 요소를 두 번 탐색하여 중복을 검사하는 방법이다.

@Test
void duplicateTest() {
    List<Integer> list = List.of(1, 2, 3, 4, 5, 1);

    boolean flag = false;
    for (int i = 0; i < list.size() - 1; i++) {
        int n1 = list.get(i);
        for (int j = i + 1; j < list.size(); j++) {
            int n2 = list.get(j);
            if (n1 == n2) {
                flag = true;
            }
        }
    }

    System.out.println("duplicate objs : " + flag);
}

각 요소를 순차적으로 탐색하면서 리스트를 다시 순회하게 된다.
이 방법은 읽기에 다소 불편하고, 시간 복잡도가 O(n²)이다.

 

2. Set을 이용하기

현재 목표는 “중복 요소를 확인하자”이다.

이중 반복문은 직관적이지만, 시간 복잡도가 높기 때문에 더 빠른 연산을 위해 Set을 이용할 수 있다.

 

Set은 중복된 값을 허용하지 않기 때문에 중복 확인에 적합하다.
Set 중에서도 `HashSet`을 이용하여 중복값을 확인하면 된다.

HashSet의 키 중복을 확인하는 로직은 평균적으로 O(1)의 시간 복잡도를 가진다.
물론, 해시 충돌로 인해 모든 요소가 동일한 버킷에 저장되는 경우 O(n)까지 증가할 수 있지만, 일반적으로는 O(1)이다.

@Test
void duplicateTestWithSet() {
    List<Integer> list = List.of(1, 2, 3, 4, 5, 1);

    Set<Integer> set = new HashSet<>();
    boolean flag = false;
    for (int i = 0; i < list.size(); i++) {
        boolean addResult = set.add(list.get(i));
        if (!addResult) {
            flag = true;
        }
    }

    System.out.println("duplicate objs : " + flag);
}

 

Set의 add 메서드는 중복된 요소가 이미 존재할 경우 false를 반환한다.
이를 이용하여 중복 요소를 효율적으로 확인할 수 있다.

 

3.시간 차이 비교하기

시간 차이가 실제로 얼마나 큰지 알아보기 위해 약간의 실험을 해보았다.

private List<Integer> list;

@BeforeEach
public void setUp() {
    list = new ArrayList<>();
    IntStream.range(0, 100_000).forEach(i -> list.add(i));
    list.add(100000 - 1);
}

@Test
void duplicateTest() {

    boolean flag = false;
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < list.size() - 1; i++) {
        int n1 = list.get(i);
        for (int j = i + 1; j < list.size(); j++) {
            int n2 = list.get(j);
            if (n1 == n2) {
                flag = true;
                break;
            }
        }
    }
    long endTime = System.currentTimeMillis();

    System.out.println("duplicate objs : " + flag);
    System.out.println("time taken : " + (endTime - startTime));
}

@Test
void duplicateTestWithSet() {

    Set<Integer> set = new HashSet<>();
    boolean flag = false;
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        boolean addResult = set.add(list.get(i));
        if (!addResult) {
            flag = true;
            break;
        }
    }
    long endTime = System.currentTimeMillis();

    System.out.println("duplicate objs : " + flag);
    System.out.println("time taken : " + (endTime - startTime));
}

리스트 길이가 100,001일 때 약 500배 이상의 시간 차이가 났다.
앞으로는 HashSet을 자주 이용하는 것이 좋겠다고 생각했다.

 

4. TreeSet은 어떨까?

TreeSet은 삽입 및 검색 시 항상 O(log n)의 시간 복잡도를 유지한다.

@Test
void duplicateTestWithTreeSet() {

    Set<Integer> set = new TreeSet<>();
    boolean flag = false;
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        boolean addResult = set.add(list.get(i));
        if (!addResult) {
            flag = true;
            break;
        }
    }
    long endTime = System.currentTimeMillis();

    System.out.println("duplicate objs : " + flag);
    System.out.println("time taken : " + (endTime - startTime));
}

 

TreeSet은 HashSet보다 약 두 배 이상 느린 결과를 보여주었다.
따라서, 중복 요소를 확인할 때는 상황에 따라 적절한 자료구조를 선택하는 것이 중요하다.