[LeetCode] 80. Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II - LeetCode

int 배열이 주어지면 최대 2개까지의 중복만 허용하여 배열을  재구성하는 문제입니다.

추가적인 메모리 할당은 O(1)만 허용됩니다.

 

입출력 예시

입력 : [1,1,1,2,2,3]
출력 : [1,1,2,2,3]

 

문제접근

투 포인터를 활용하여 풀어보려고 했습니다.

배열을 탐색하며 값을 변경할때 투포인터가 유용하게 사용된다고 생각하기 때문입니다.

추가적으로 2개 이상으로 중복이 되었는지 확인이 필요하기위한 변수도 하나 사용하였습니다.

 

1. for문을 탐색하면서 i와 i-1의 데이터가 일치하면 중복값이라고 판단
   
   • 일치하지 않으면 limit 초기화
2. 중복이 허용될때만 inputIdx에 값을 할당
3. 최종적으로 중복이 제거된 위치인 inputIdx를 반환 

 

    public int removeDuplicates(int[] nums) {
        int limit = 1; // 2개 이상인지 확인
        int inputIdx = 1; // 값이 들어갈 인덱스

        for (int i = 1; i < nums.length; i++) {
            // 뒤에있는 데이터와 비교해서 값이 다르면 중복이 아니므로 limit 초기화
            if (nums[i] > nums[i - 1]) {
                limit = 1;
            } else {
                // 뒤에있는 데이터와 비교해서 값이 같으면 중복이므로 limit++
                limit++;
            }

            // 중복이 허용될때만 적용
            if (limit <= 2) {
                // 같은값이면 바꿀필요가 없음
                if (nums[i] > nums[inputIdx]) {
                    nums[inputIdx] = nums[i];
                }
                // 다음 들어온 인덱스를 바라보게 변경
                inputIdx++;
            }
        }
        return inputIdx;
    }

 

 

시간복잡도

for문을 사용해 nums의 길이만큼 한번 탐색을 하고있습니다. 

이 코드의 시간복잡도는 O(n)입니다.

 

공간복잡도

마찬가지로 공간복잡도는 O(n)입니다.

 

 

다른사람의 풀이

저는 투포인터와 limit변수를 사용해서 2개의 중복제한을 했습니다.

하지만 모범답안은 limit변수를 사용하지않고 해결하였습니다.

 

시간복잡도는 같지만, 공간복잡도에서 변수 1개의 공간을 제가 작성한 코드보다 효율적으로 사용하고있습니다.  

동시에 가독성도 높아졌습니다.

 

현재 요소가 인덱스-2의 요소와 같지 않다면 이 요소를 아직 두 번 접하지 않았기 때문에
결과 배열에 포함하여 중복을 제거할 수 있습니다.

 

    public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) {
            return nums.length;
        }

        int index = 2;

        for (int i = 2; i < nums.length; i++) {
            if (nums[i] != nums[index - 2]) {
                nums[index] = nums[i];
                index++;
            }
        }

        return index;
    }

 

시간복잡도

for문을 사용해 nums의 길이만큼 한번 탐색을 하고있습니다. 

이 코드의 시간복잡도는 O(n)입니다.

 

공간복잡도

마찬가지로 공간복잡도는 O(n)입니다.

 

 

마무리

이번 문제는 정말 어려웠습니다...

투포인터와 중복의 갯수제한을 하면서도 공간복잡도를 생각해야하니 머리가 복잡해졌습니다.

 

알고리즘을 계속 풀어보면서 효율적인 생각들을 떠올리는 연습을 꾸준히 해야겠습니다.

 

참고

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/solutions/3921824/simple-easy-100-beats-java-solution/?envType=study-plan-v2&envId=top-interview-150