[LeetCode] Arrays101 - Remove Element

Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

 

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

 

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length. For example if you return 2 with nums = [2,2,3,3] or nums = [2,2,0,0], your answer will be accepted.

 

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]
Explanation: Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.

 

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

 

---

 

배열에서 특정 값을 찾아서 삭제를 하거나 아니면 맨 뒤로 보내버리고,

나머지 값들의 개수를 리턴하는 문제이다.

역시나 어려운 이유는 In-place로 풀어야한다는 점 때문...

 

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === val) {
            nums.splice(i, 1);
            i--;
        }
    }
    
    return nums.length;
};

 

이렇게 JavaScript에 내장된 splice 메소드를 사용하면 3분만에 쉽게 풀 수 있지만

이 메소드를 사용하지 않고 풀어내는 방법이 있을게 분명하니 또 머리를 쥐어뜯으며 고민을 시작했다.

 

 

 

그래서 처음 생각해낸 방법은 이런 방법이다.

앞에서부터 순회를 하다가 2를 만나면 바로 다음 인덱스부터 2가 아닌 값을 찾아서 swap을 하는 방식이다.

단점은 바로 다음 2를 찾는 일이 너무 에너지를 많이 소모해서 효율성이 좋지 않다는 점이다.

이 방법을 코드로 표현하면 다음과 같다.

 

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var findIndex = function(array, startIndex, condition) {
    for (let i = startIndex; i <= array.length - 1; i++) {
        if (condition(array[i])) return i;
    }
    return -1;
};

var swap = function(array, index1, index2) {
    const temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
};

var removeElement = function(nums, val) {
    let valIndex = 0;

    for (let i = 0; i <= nums.length - 1; i++) {
        if (nums[i] === val) {
            const nextItemIndex = findIndex(nums, i + 1, (item) => item !== val);

            if (nextItemIndex === -1) break;
            valIndex++;
            swap(nums, i, nextItemIndex);
        } else {
            valIndex++;
        }
    }
    
    return valIndex;
};

 

딱 봐도 그닥 효율이 좋아보이진 않는다.

 

그래서 다시 고민 고민하다가 생각한 더 나은 방법은 앞뒤에서 동시에 탐색을 하는 방법이다.

 

 

그러니까 앞에서 시작하는 탐색은 2가 발견할 때까지 index를 더하면서 탐색을 하고,

뒤에서 시작하는 탐색은 2가 아닌 값을 발견할 때까지 index를 빼면서 탐색한다.

 

그리고 앞에서 2를 발견하고 뒤에서 2가 아닌 값을 발견하면 두 값을 swap한다!

 

이걸 startIndex가 endIndex보다 작거나 같을 때까지 반복하고 나면

최종적으로는 startIndex가 2가 아닌 값들의 개수가 된다.

 

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let startIndex = 0;
    let endIndex = nums.length - 1;
    
    while (startIndex <= endIndex) {
        if (nums[startIndex] === val && nums[endIndex] !== val) {
            const temp = nums[startIndex];
            nums[startIndex] = nums[endIndex];
            nums[endIndex] = temp;
        }
        
        if (nums[startIndex] !== val) {
            startIndex++;
        }
        if (nums[endIndex] === val) {
            endIndex--;
        }
    }
    
    return startIndex;
};

 

 

여기까지 해놓고 이만하면 잘 풀었다고 너무 좋아했는데

솔루션을 보니 훨씬 더 간단하게 해결할 수 있었다는걸 알게되었다.ㅠㅠ

 

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

그러니까 위 문장이 이 문제에서 아주 중요한 부분이었다...

나는 꾸역꾸역 swap을 해서 문제를 해결했는데,

사실 굳이 swap을 할 필요없이 뒤에서부터 2가 아닌 값을 찾아서 앞의 2를 덮어쓰기만 하면 되는거였다.

왜냐면 뒤에 있는 값에 뭐가 들어있던 상관이 없으니까..!

 

 

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let startIndex = 0;
    let endIndex = nums.length - 1;
    
    while (startIndex <= endIndex) {
        if (nums[startIndex] === val) {
            nums[startIndex] = nums[endIndex];
            endIndex--;
        } else {
            startIndex++;
        }
        
    }
    
    return startIndex;
};

 

 

그리고 진짜 코드로는 제일 간단해보였지만 이해하기는 제일 어려웠던 방법은 다음과 같은 방법이다.

(이 방법이 가능한 이유는 아이템의 순서를 신경쓰지 않아도 되기 때문이다.)

 

이 방법은 너무 헷갈려서 진짜 index 하나 하나를 종이에 그려가면서 이해했다.ㅠㅠ

 

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let i = 0;
    
    for (let j = 0; j < nums.length; j++) {
        if (nums[j] !== val) {
            nums[i] = nums[j];
            i++;
        }
    }
    
    return i;
};

 

포인터를 i랑 j 2개로 두고 j는 계속 1씩 증가하되, i는 j번째 아이템이 val이 아닐때만 1씩 증가한다.

그리고 j번째 아이템이 val이 아닐 때 j번째 아이템을 i번째 아이템으로 덮어쓰는 방법이다.