한빛출판네트워크

이전글 [독자가 풀어보는 "자바로 배우는 핵심 자료구조와 알고리즘" 2회] 실습에 사용된 MyArrayList 코드는 깃헙을 통해 확인할 수 있습니다.

  

앞서 2장에서 다룬 내용을 끝으로 ArrayList에 대한 구현을 마치려 했는데, 뒷 부분의 removeAll(Collection) 메서드에서 알고리즘이 기존에 단순했던것에 비해 생각이 필요한 부분이 있어 마지막으로 내용을 다루어 보았다.

removeAll

우선 removeAll(Collection)에 대해서 알아보자.

 

java docs

 

먼저 removeAll에 대한 상세를 간단히 살펴보면,

 

boolean removeAll(Collection<?> c)

Removes from this list all of its elements that are contained in the specified collection (optional operation).

컬렉션에 포함된 리스트의 전체 요소를 제거한다.

여기서 주의할 것이 있는데, removeAll() 과 clear() 함수는 엄연히 다르다.

clear() 함수는 말그대로 전체 리스트를 비워버리는 것이고, removeAll은 전체 리스트 중 특정 collection에 포함된 요소들만 제거한다는 것이다.

 

Parameters: 

c - collection containing elements to be removed from this list

리스트의 컬렉션 중 제거될 요소들을 인자값으로 받는다.

 

Returns: 

true if this list changed as a result of the call

리스트가 변경되면 true를 반환 한다.

 

테스트 코드

 

이제 본격적으로 테스트코드를 클리어해보자.

 

    @Before

        public void setUp() throws Exception {

            mylist = new MyArrayList<>();

            mylist.add(1);

            mylist.add(2);

            mylist.add(3);

    //        mylist.addAll(list);

        } 

    

        @Test

        public void testRemoveAll() {

            mylist.removeAll(list);

            assertThat(mylist.size(), is(0));

        }

 

테스트 코드가 간결하다.

리스트를 제거했고, 그 리스트의 사이즈가 '0' 인지를 검증하면된다.

그런데 removeAll을 구현하려고 보니, remove(Object) 메서드 구현이 선행되어야 할 것 같다.

 

remove

다음은 remove(Object) 내용이다.

 

java docs

 

boolean remove(Object o)

Removes the first occurrence of the specified element from this list, if it is present (optional operation). If this list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists). Returns true if this list contained the specified element (or equivalently, if this list changed as a result of the call).

리스트에서 해당 요소가 존재한다면, 최초로 발생하는 요소를 제거한다. 만약 해당 요소가 존재하지 않으면 변경되지 않는다.

공식적으로 해당 요소가 존재한다면, 인덱스가 가장 낮은 요소가 제거된다(o==null ? get(i)==null : o.equals(get(i)))).

리스트에 해당 요소가 존재한다면 true를 반환한다. (리스트가 변경된 경우도 마찬가지)

 

Parameters:

o - element to be removed from this list, if present

리스트로부터 제거될 요소 (존재한다면)

 

Returns:

true if this list contained the specified element

해당 요소를 포함하고 있는 경우 true 반환

 

테스트 코드

 

remove(Object) 의 테스트 코드부터 처리해보자.

 

    @Test

        public void testRemoveObject() {

            boolean flag = mylist.remove(new Integer(2));

            assertThat(flag, equalTo(true));

            assertThat(mylist.size(), is(2));

            assertThat(mylist.get(1), is(new Integer(3)));

            //System.out.println(Arrays.toString(mal.toArray()));

    

            flag = mylist.remove(new Integer(1));

            assertThat(flag, equalTo(true));

            assertThat(mylist.size(), is(1));

            assertThat(mylist.get(0), is(new Integer(3)));

            //System.out.println(Arrays.toString(mal.toArray()));

    

            flag = mylist.remove(new Integer(5));

            assertThat(flag, equalTo(false));

            assertThat(mylist.size(), is(1));

            assertThat(mylist.get(0), is(new Integer(3)));

            //System.out.println(Arrays.toString(mal.toArray()));

    

            flag = mylist.remove(new Integer(3));

            assertThat(flag, equalTo(true));

            assertThat(mylist.size(), is(0));

            //System.out.println(Arrays.toString(mal.toArray()));

        }

 

코드는 길지만, 어려울 것 없다.

• 리스트의 요소를 제거하고
• 해당 결과가 정상적으로 처리되었는지 검증
• 사이즈가 변경되었는지 검증
• 제거된 만큼 배열의 요소가 이동했는지 검증

테스트코드에서 친절하게 내가 처리해야할 로직을 설명해주고있다.

 

구현

 

그럼 바로 구현해보자.

 

    @Override

        public boolean remove(Object o) {

            boolean flag = false;

    

            for(int i=0; i<size; i++){

                if(array[i].equals(o)){

                    remove(i);

                    flag = true;

                }

            }

            return flag;

        }

 

일단 index가 작은것부터 검증을 해야하기 때문에 반복문은 0부터 시작해야한다.

배열의 요소가 같은지를 검증하면 되고, 같으면 이전에 구현해놓았던 remove(index) 메서드를 이용해서 처리해줄 수 있다.

처리가 되면, 요구사항대로 true를 리턴해주면 큰 문제없이 처리된다.

그러면 이제 결과코드와 비교해보자.

 

    @Override

      public boolean remove(Object obj) {

        int index = indexOf(obj);

        if (index == -1) {

          return false;

        }

        remove(index);

        return true;

      }

 

이번엔 크게 잘못 처리한 것 같다.

우선 내가 구현한 코드는  반복문이 돌면서 하나씩 검증하고, equals가 존재할 경우 다시 remove(index) 함수에서 한번 더 반복문이 실행된다.

즉, remove(Object) 에서 n번 실행된 후 remove(index) 에서 n번 실행된다. 이것은 이차알고리즘 O(n^2) 이라는 말이다.

아주 비효율적인 시간복잡도를 보인다.

하지만 결과코드에서는 indexOf(Object)와 remove(index) 를 사용했다.

 

indexOf 역시 선형 알고리즘이고 마찬가지로 remove(index) 두 개의 선형알고리즘이 사용되지만, indexOf에서 '-1'의 결과가 나올경우 아래의 remove(index)는 실행되지 않는다.

 

이렇게 특수한 경우를 어떻게 계산해야할까...?

 

removeAll 구현

 

자 그러면 다시, removeAll(Collection) 메서드로 돌아가서 remove(Object)를 통해 처리해보자.

 

    @Override

        public boolean removeAll(Collection<?> c) {

            boolean flag = false;

    

            for(Object o : c){

                flag  = remove(o);

            }

            return flag;

        }

 

remove(Object)를 구현하기 전에는 removeAll을 처리하는게 까다로웠다.

(사실 remove(Object)를 구현해야할 것 같다는 느낌적인 느낌이 있었지만, 귀찮아서 미루었던건 안비밀)

remove(Object) 메서드만을 이용하면 손쉽게 처리될 수 있다.

그런데 결과코드에서 처음보는 연산자를 보았다.

 

    @Override

      public boolean removeAll(Collection<?> collection) {

        boolean flag = true;

        for (Object obj: collection) {

          flag &= remove(obj);

        }

        return flag;

      }

 

 

&= 사실 처음보는 연산자다.

좌변과 우변이 &조건이니까, 양쪽다 true일때만 true를 리턴하는 것이다.

부끄럽게도 처음보는 연산자인데 앞으로 꽤 요긴하게 쓰일 것 같다.

 

알고리즘

 

removeAll(Collection)의 알고리즘 시간복잡도를 계산할 때 주의할 것이 있다.

앞서 remove(Object)와 비슷한 접근이겠지만, removeAll 의 로직을 살펴보자.

 

collection(위 예제는 List)의 길이가 n개 이고,

remove(Object)에서 제거될 요소가 m개 존재한다고 한다면, 이 알고리즘의 시간복잡도는 O(nm) 이다.

 

즉 이 말은 collection(List)의 크기가 상수라면, removeAll 메서드는 선형알고리즘(O(nm)) 이 된다.

(예를들어 List의 길이가 100이고, 제거할 요소가 m개 있다면 O(100m) -> 알고리즘 계산시 상수값은 무시되니 O(m) 으로 계산될 것이다.)

하지만 List의 크기가 n에 비례한다면 removeAll의 시간복잡도는 O(n^2) 즉, 이차 알고리즘이 되는 것이다.

 

책에 아주 중요한 내용이 담겨있는데, 

 

반복문이 1개 라면 보통 선형 알고리즘 O(n)이다.

반복문이 2개가 중첩되어 있다면 보통 이차알고리즘 O(n^2) 이다.

 

하지만 반복문이 몇 번 실행되었는지 주목해야 한다.

반복문의 횟수가 모든 반복문에 대해 n에 비례한다면, 반복문의 개수만 세면되지만

항상 n에 비례하지 않는 경우 (remove(Object)와 같이) 조금 더 주의깊게 살펴봐야 한다.