[LeetCode] 26 Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array - LeetCode

 

주어진 int형 배열에 중복값을 제거하여 반환하는 문제입니다.

중복이 제거된 배열의 길이를 리턴하고 원본 배열에는 순서대로 중복 제거된 데이터가 있어야합니다.

 

문제풀이

문제에서는 배열할당에 대한 언급이 없었으므로 set을 사용할지 ArrayList의 contain을 사용할지 고민하였습니다.

Set을 사용한다면 공간복잡도가 높아지지만 중복에대한 계산을 하지 않아도 되기 때문에 시간복잡도는 줄어들 것입니다.

ArrayList는 공간복잡도도 높아지고 contain함수는 O(n)의 시간복잡도가있기때문에 시간복잡도도 높아집니다.

이번에는 둘 다 사용하지 않았습니다..

 

Stream을 이용해 간단하게 중복을 제거할 수 있기 때문입니다.

 

Modern Java In Action에서 봤던것처럼 Stream에 원시타입을 사용하는것은 별로 좋지 않은 방법입니다.

하지만 시간을 확인해보려고 시도해 보았습니다.

 

 public int removeDuplicates(int[] nums) {
        final int[] temp = Arrays.stream(nums)
                .distinct()
                .toArray();

        for (int i = 0; i < temp.length; i++) {
            nums[i] = temp[i];
        }

        return temp.length;
    }

  

하위 5.68 입니다...

왜 느려진 것일까요?

 

Stream은 내부적으로  제네릭 타입을 파라미터로 받고 있고, 파라미터는 클래스 형식입니다.

따라서 wrapper 클래스로 맞춰 형변환의 과정이 추가적으로 들어갑니다...

 

또한 클래스 형식이다? 라는것은 Heap메모리에서 관리하겠다는 뜻입니다.

Heap메모리는 모든 스레드가 공유하는 자원이기에 내부적으로 락을 관리하는 경우도 있을 것입니다.

 

이러한 이유로 단순히 for-loop를 반복하는것보다 시간이 더 걸리는 것입니다. 

 

다른 사람의 코드

현재 확인하는 nums의 인덱스와 인덱스 -1이 중복이 아니라면
count의 위치와 i의 위치에 있는 데이터를 교환하는 방식입니다. 

 

여기서 count는 중복되지 않은 값을 넣을 인덱스를 가리킵니다.

중복이 아닐경우에만 count의 위치에 i값을 넣어주면 count번째까지는 중복이 없게 됩니다.

 

    public int removeDuplicates(int[] nums) {
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[count++] = nums[i];
            }
        }
        return count;
    }

 

시간복잡도

nums를 loop문으로 한번 탐색하고있습니다.
O(n)의 시간복잡도가 필요합니다.

 

공간복잡도

추가적인 배열없이 문제를 해결하였습니다.

O(n)의 공간복잡도가 필요합니다.

 

느낀점

이번에도 느끼지만 투포인터를 잘 활용하면 많은 이점을 얻을수 있다는것을 깨달았습니다.

또한 원시타입이 스트림을 사용할때 왜 시간이 오래걸리는지 깨달았습니다.   

 

참고

java stream이 for-loop보다 느린 이유