문제

전에 풀었던 26. Remove Duplicates from Sorted Array 문제와 거의 동일하다. 다른점은 중복을 제거하되 최대 중복을 2개까지 허용하는 것이다.

예를들어 nums = [1,1,1,2,2,3]이라면 중복을 최대 2개까지 허용하면서 제거하면 nums = [1,1,2,2,3,x]가 되고 제거되지 않은 원소의 개수인 5를 리턴하면 된다.

하지만 조건이 하나 더 있다. 문제를 해결하기 위해 어떠한 배열도 할당해서는 안된다. 공간복잡도를 $O(1)$을 유지하면서 기존에 주어진 nums 배열을 사용해 해결해야한다.

첫 풀이

첫 풀이 역시 저번 문제와 거의 유사하다. 한 가지 다른 점은 equalCnt 변수를 사용해 중복된 값이라도 2개까지 허용하도록 처리한 것이다. k 변수를 사용해 제거되지 않고 남은 원소의 개수이면서 원소가 들어가야할 인덱스를 관리한 것은 동일하다. 시간복잡도는 $O(n)$이며 공간복잡도 또한 $O(1)$로 문제의 조건에 맞추었다.

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 1;
        int equalCnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[k++] = nums[i];
                equalCnt = 1;
            } else {
                if (equalCnt < 2) {
                    nums[k++] = nums[i];
                    equalCnt++;
                }
            }
        }

        return k;
    }
}

결과로는 속도는 빨랐지만 메모리는 다소 낮게 나왔다.

두번째 풀이

첫 풀이에서 공간복잡도가 $O(1)$임에도 메모리가 낮게 나와서 첫 풀이를 좀 더 개선해보려고 노력했다. 개선한 방법은 equalCnt를 사용하지 않는 방법이다. 방법은 간단하다. 선택된 원소가 이미 2번 살아남았다면 nums[k - 2]에 이미 선택된 원소가 위치해 있을 것이다. 따라서, 선택한 nums[i]의 원소와 nums[k - 2]의 원소가 같지 않으면 살아남을 수 있는 원소인 것이다.

시간복잡도와 공간복잡도는 마찬가지로 $O(n)$과 $O(1)$으로 동일하지만 첫 풀이보다 int형 변수를 하나 줄이면서 코드 또한 간단하게 할 수 있었다.

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 2;
        for (int i = 2; i < nums.length; i++) {
            if (nums[k - 2] != nums[i]) {
                nums[k++] = nums[i];
            }
        }

        return k;
    }
}

하지만 결과는

로 첫 풀이보다 0.1MB를 줄일 수 있었지만 거의 동일한 결과가 나왔다.

다른 Solution들과 비교

나랑 똑같이 풀이한 것도 많았고 좀 더 직관적으로 풀어 작성한 풀이들도 많았다. 이상한 점은 나는 변수를 k 하나만 사용했지만 풀어쓴 풀이에서는 두 개의 변수를 사용했음에도 나보다 메모리가 적게 나온 경우가 있었다. 가장 큰 요인은 LeetCode에서 실행하면서 항상 동일한 결과를 도출할 수 없기 때문에 그런 것 같다. 위와 동일한 코드를 여러번 제출했을 때 메모리가 43.5 MB까지 나왔었다.

내가 가장 메모리가 적게 나왔던 시도는 43.2 MB였다. 이 시도는 이전 코드와 약간 다르다. 기존 코드의

if (nums[k - 2] != nums[i]) {
	nums[k++] = nums[i];
}

부분을

if (nums[k - 2] != nums[i]) {
	nums[k] = nums[i];
    k += 1;
}

로 수정했을 때 가장 적은 메모리가 나왔다.

정확하진 않지만 나의 예상으로 ++ 연산자의 동작으로 인해 그럴 가능성이 있을 것 같다. stack overflow에서 본 것 중에서 ++ 연산자(후위증가 연산의 경우)는 다음과 같이 동작한다고 한다.

temp = k;
k = k + 1;
retur temp;

이 과정에서 임시 변수를 하나 선언되기 때문에 k += 1로 수정했을 때 메모리가 가장 적게 나온 것이 아닌가 생각한다.

후위증가연산의 동작방식을 정확히 알고싶어 찾아봤지만 실패하였다.. 다음에 기회가 된다면 정확히 찾아봐야겠다.