LeetCode 27 - Remove Element

https://leetcode.com/problems/remove-element

int[] nums 배열에서 int val과 같은 값을 제거하는 문제이다.

특이한 점은 removeElement의 리턴 타입이 int인데 정답 처리가 리턴 값만 맞으면 되는 것이 아니라는 점이다.

추가로 val과 같은 값이 제거된 nums 배열이 in-place 형태로 즉 추가 공간 사용 없이 내부에서 수정돼야 한다.

예를 들어보자.

nums = {0, 1, 2, 2, 3, 0, 4, 2} 이고 val = 2 일 때이다.

nums에서 2를 제거하게 되면 {0, 1, _, _, 3, 0, 4, _}가 되고 이게 최종적으로 {0, 1, 4, 0, 3, _, _, _} 이 돼야 한다. 그리고 리턴 값은 제거되지 않은 유효 숫자인 0, 1, 4, 0, 3의 개수인 5가 된다.

또한 nums의 정렬 순서는 중요하지 않다. 어차피 정답 판정 시에 유효 범위에서 정렬 작업이 수행된다. 위의 예시에서는 {0, 1, 3, 0, 4}가 나오던 {0, 1, 4, 0, 3}가 나오던 문제없다는 것이다.

대신 int[] nums를 조작하는 것이기 때문에 ‘_’라는 부분은 임의의 숫자가 들어가도 괜찮고 정렬이 0, k (k는 유효한 숫자의 개수)에서 동작해서 정답 판정이 들어가기 때문에 유효한 숫자들이 앞에서부터 자리를 차지하고 있어야 한다는 점을 주의해야 한다.

그냥 시키는 대로 풀기

그냥 시키는 대로 풀어보자. nums에서 val을 제거하고 정렬하면 된다.

우선 문제의 조건을 보니 nums의 원소는 최대값이 50이다. 제거되지 않은 요소들을 앞에 두기 위해 제거되는 요소들의 값을 51로 바꾼 다음 정렬하면 자연스럽게 제거되지 않은 요소들만 앞으로 가게 된다.

class Solution {
    static final int MAX = 51;
    public int removeElement(int[] nums, int val) {
        int k = nums.length; // 유효값 카운트
        for (int i = 0; i < nums.length; i++) { // 여기서 i < k를 쓰면 안된다. k값은 계속 변한다.
            if (nums[i] == val) {
                nums[i] = MAX;
                k--; // 전체 갯수에서 하나가 제거됐다.
            }
        }
        Arrays.sort(nums); // 제거되지 않은 값들이 자연스럽게 0~k 범위 내로 몰린다.
        return k;
    }
}

문제없이 정답이지만 이게 좋은 풀이일까? 문제의 설명을 보면 정답을 판정하는 과정에서 (0, k) 사이의 정렬이 한번 일어난다.

이 말은 nums가 정렬되지 않은 상태로 반환 돼도 괜찮다는 것이다.

그런데 위의 풀이에서는 쓸데없이 정렬 작업이 한 번 들어가고 있다. 결국 시간복잡도는 O(NlogN)이 된다.

심지어 nums[i] 를 MAX로 바꾸는 것은 편법에 가깝다는 생각이 든다.

앞에만 몰아 넣으면 된다.

생각해 보자. 유효한 숫자는 앞에 순서에 상관없이 몰아넣으면 된다.

유효하지 않은 숫자는 변경할 필요 없이 뒤로 몰아 넣으면 된다.

이 두 작업을 투 포인터를 이용해서 할 수 있다.

class Solution {
    static final int MAX = 51;
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            if (nums[left] == val) {
                // val을 right 위치의 값으로 덮어 씌운다.
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }

        return left;
    }
}

코드를 보면 두 개의 포인터가 이동하고 있다. 목표는 앞의 위치의 val을 제거하는 것이다. 따라서 nums [left]의 값이 val과 일치한다면 nums [right]의 값으로 덮어 씌운다.

여기서 nums[right]가 val과 동일하더라도 상관없다. left의 위치가 그대로 이므로 다음번 검사 때 감소된 right의 위치와 비교를 통해 새롭게 덮어 씌워질 것이다.

이 방법을 통해 시간복잡도를 O(N)으로 줄일 수 있었다.