문제

오름차순으로 정렬된 nums 배열에서 중복된 값을 제거하고 난 뒤 nums 배열의 0 ~ k-1(k = 중복을 제거한 뒤 남은 원소들의 개수) 인덱스의 원소들이 중복을 제거한 유일한 원소들로 채워져야 한다.

예를들어, nums = [0,0,1,1,1,2,2,3,3,4] 배열이 있을 때 중복을 제거한 뒤에 nums 배열은 nums = [0,1,2,3,4,x,x,x,x,x] 값이 되며 k = 5를 리턴해야한다.

풀이

문제를 보자마자 최근 풀었던 LeetCode 27. Remove Element와 유사하게 풀 수 있겠다는 생각이 들어서 바로 적용해보았고 마찬가지로 시간복잡도는 $O(n)$이다.

저번 문제와 차이점은 제거해야할 기준이다. 저번 문제에서는 val에 해당하는 값을 지웠지만 이번에는 중복된 값을 제거해야한다. 중복된 값의 기준은 직전 인덱스의 원소와 같은지 확인하고 같다면 지우면 된다. nums 배열이 오름차순으로 정렬되어 있기때문에 직전 인덱스의 원소와 같음만 비교하더라도 모든 중복을 제거할 수 있다.

또한, 중복이 제거되고 난 뒤 유일한 원소들은 0 ~ k-1 인덱스에 차례로 위치해야하기 때문에 저번 문제와 마찬가지로 지워진 원소의 개수만큼 앞으로 이동하도록 하였다.

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

        return nums.length - removeCnt;
    }
}

결과는

개선하기

저번에 열심히 풀고나서 다른 Solution을 봤을 때 어렵게 작성했던 코드가 쉽게 작성될 수 있었어서 허무했었다. 그래서 이번에는 조금 더 간단한 방법이 없을지 고민했다.

풀이에서 유일한 값을 앞으로 이동시키는데 removeCnt의 값을 활용했다. 유일한 원소들의 개수 k를 리턴하는 데도 removeCnt 값을 활용했다. 조금만 달리 생각해보면 제거된 원소들의 개수가 아닌 유일한 원소들의 개수를 활용할 수 있다. 즉 if (nums[i] == nums[i - 1])로 비교하는 것은 동일하되 지운 원소의 개수 removeCnt를 증가시키는 것이 아닌 유일한 값이 들어가야하는 인덱스이자 유일한 원소의 개수(k)를 관리하면 된다.

이렇게 개선하게되면 if-else문이 아닌 하나의 if문으로 처리할 수 있게 되며 자연스럽게 유일한 원소의 개수(k)도 구해지므로 바로 k를 리턴할 수 있게 된다.

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

        return k;
    }
}

이 풀이가 시간복잡도가 $O(n)$이며 공간복잡도가 $O(1)$로 가장 최적인 방법인 것 같았다. 다른 Solution을 확인해보니 모두 같은 방식을 사용하고 있었다.