LeetCode : 80. Remove Duplicates from Sorted Array II

문제 링크

문제 먼저 읽기

• 오름차순으로 정수 nums 가 주어진다.
• 각 고유 요소가 최대 두 번만 나타나도록 중복된 요소를 같은 배열안에서 제거합니다. 요소의 상대적 순서는 동일하게 유지해야 합니다.
• java는 배열 길이를 변경할 수 없으므로, 결과를 배열 nums의 index 0부터 배치합니다.
• 중복 제거한 후 요소가 개수를 반환합니다.

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]

어떻게 풀까?

생각

• 이제 요소가 몇개씩 가능한지 저장해야합니다.
• 순서를 그대로 유지하며 저장되는 개수를 저장해야하므로, 지금 포인터가 요소를 저장할 수 있는 개수를 초기화하며 풀 수 있지 않을까요?
• 별도의 자료구조를 더 정의하는 것은 메모리를 추가로 더 사용하므로 지양하였습니다.

수도코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int curl = 1;
        int stored = 2;
        for (int p=1; p<nums.length; p++) {
            nums[curl++] = nums[p];

            if (nums[p-1] == nums[p]) {
                stored --;
            }
            if (nums[p-1] != nums[p]) {
                stored = 2;
            }
            if (stored == 0) curl --; // 저장가능한 개수가 0이되면 포인터를 뒤로 옮겨서 다음 숫자가 덮어 쓸 수 있도록 한다.
        }
        return curl;
    }
}

결과

💡 **Wrong Answer**

• 테스트는 통과했지만, 실제 Submit 을 했는데 실패했다.

Input:
[0,0,1,1,1,1,2,3,3]
Output:
[0,0,1,1,1,2,3,3]
Expected:
[0,0,1,1,2,3,3]

• stored 변수 관리에서 실패한 것 같아서 다시 의사 코드를 짜기로했다.

수도코드 2차

class Solution {
    public int removeDuplicates(int[] nums) {
        int curl = 1; // 두번째 요소부터 입력한다.
        int ability = 2;
        for (int p=1; p<nums.length; p++) {
            nums[curl] = nums[p]; // 먼저 입력한다.

            if (nums[curl-1] == nums[p]) { // 이전 입력값과 같으면 저장가능한 숫자를 줄인다.
                ability --;
            }
            if (nums[curl-1] != nums[p]) { // 만약 다르다면 저장 가능한 숫자를 초기화한다.
                ability = 2;
            }

            if (ability > 0) curl ++; // 만약 더 저장할 수 있다면 입력 포인터를 늘려 다음 자리를 채운다.
        }
        return curl;
    }
}

결과 2차

💡 **Success**

Runtime: 1 ms, faster than 22.23% of Java online submissions for Remove Duplicates from Sorted Array II.
Memory Usage: 43.3 MB, less than 95.63% of Java online submissions for Remove Duplicates from Sorted Array II.

 

다른 풀이 방식과 문제 회고

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums <= 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];
            }
        }

        return index;
    }
}

• 이번에는 공간복잡도는 좋은 편이었으나, 시간 복잡도가 다른 사람의 풀이에 대해 많이 떨어졌다.
• nums 길이가 짧을 때 처리와 포인터 방식이 아닌 바로 2개 전 변수와 함께 비교하는 방식으로 코드를 더 단순하게 짤 수 있었다. nums가 이미 정렬되어 있으므로 가능한 방법이었다.