[Java] ConcurrentModificationException 원인과 해결

[문제 상황]

프로그래머스 체육복문제를 풀고 채점해보니 몇개의 테스트코드에서 시간초과가 났다.
 
[문제가 발생한 부분]

 for(int i=0;i<len;i++){
            int tmp = lost_list.get(i);
           if(reserve_list.contains(tmp-1)){
                answer++;
                int index = reserve_list.indexOf(tmp-1);
                reserve_list.remove(Integer.valueOf(tmp-1));
            }
            else if(reserve_list.contains(tmp+1)){
                answer++;
                int index = reserve_list.indexOf(tmp+1);
                reserve_list.remove(Integer.valueOf(tmp+1));
            }
        }

 
흔히 볼 수 있는 리스트를 순회하며 제거하는 코드라고 생각될 것이다.
이제부터 어떤 문제점이 발생하였는지 알아보자

[문제파악]

단순 시간복잡도 문제인가? 생각하고 여러가지 시도를 해보았지만 해결할 수 없었다.
결국 구글링을 하던 중, Java에서 컬렉션을 순회하는 동안 해당 컬렉션 구조가 변경되는 경우 ConcurrentModificationException이 발생할 수 있다는 사실을 알게되었다.
즉 ConcurrentModificationException 예외는 주로 컬렉션을 직접 변경하고, 이 변경이 Iterator의 내부 상태와 일치하지 않을 때 발생한다.
 
 
문제의 원인 코드를 보면 lost_list, reverse_list를 순회하다가 remove메소드를 사용해 리스트 구조가 변경되는 것을 확인할 수 있다.
 

[해결방법]

ConcurrentModificationException 해결방안은 2가지가 있는데

• 직접 수정하지말고 Iterator를 사용하여 순회 중 구조를 변경하기
• removeIf() 메소드를 사용하여 안전하게 제거하기 ->Java 8 이후

 
Iterator은 Java 컬렉션 프레임워크의  일부로, 컬렉션의 요소를 순차적으로 접근할 수 있는 인터페이스이다.
우리가 흔히  쓰는 for문, for-each문도 결국 컴파일시 iterator로 번환되어 실행된다.
Iterator를 사용하여 컬렉션 요소들을 순회, 검색, 수정 및 제거가 가능하다
 

Iterator의 주요 메소드

1. next(): 컬렉션의 다음 요소를 반환한다. 순회 중 다음 요소가 없으면 NoSuchElementException 예외를 발생시킨다.
2. hasNext(): 순회할 다음 요소가 있는지 여부를 반환한다. 이 메소드는 주로 while 루프의 조건으로 사용됩니다.
3. remove(): next() 메소드를 통해 반환된 가장 최근의 요소를 컬렉션에서 제거한다. 이 메소드는 next() 메소드 호출 직후에만 호출할 수 있으며, 호출하지 않고 remove()를 실행하면 IllegalStateException 예외가 발생합니다.

 
그럼 Iterator는 왜 컬렉션 순회중 구조 변경이 가능할까?
Iterator를 사용하여 컬렉션의 구조를 변경할 수 있는 이유는 Iterator가 컬렉션의 내부 상태를 직접 관리하기 때문이다.
 Iterator는 next() 메소드를 통해 반환한 요소에 대한 참조를 내부적으로 관리하고 있으며, remove() 메소드를 호출하면 해당 요소를 안전하게 컬렉션에서 제거할 수 있다.
이 과정은 Iterator가 컬렉션의 변경 사항을 즉시 반영하고, 이후의 순회를 계속할 수 있도록 내부적으로 조정한다.
 
[해결된 코드]

 // 남은 lostList에 대해서 체육복 빌려주기 로직
        Iterator<Integer> it = lostList.iterator();
        while (it.hasNext()) {
            int lostStudent = it.next();
            if (reserveList.contains(lostStudent - 1)) {
                reserveList.remove(Integer.valueOf(lostStudent - 1));
                it.remove();
            } else if (reserveList.contains(lostStudent + 1)) {
                reserveList.remove(Integer.valueOf(lostStudent + 1));
                it.remove();
            }
        }