LeetCode - 27. Remove Element

Problem

정수 배열 nums와 정수 val가 주어질 때, 제자리에서 nums 배열의 val를 제거하라. 그리고 val와 일치하지 않는 nums배열의 요소의 수를 리턴하라.
val와 일치하지 않는 nums배열의 요소의 수가 k라고 할때, 통과하기 위해서는 아래의 항목들을 만족해야한다.

• 처음 k개의 요소들은 val와 일치하지 않는 요소들이다. 이후 nums의 남은 요소들은 길이와 마찬가지로 중요하지 않다.
• k를 리턴하라.

Custom Judge가 솔루션을 테스트한다.

Example 1

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

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 k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores)

Solution

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

    for(let i = 0; i<nums.length; i++) {
        if(nums[i] !== val) {
            nums[k] = nums[i];
            k++;
        }
    }

    return k;
};

Explanation

처음에는 간단하게 filter 메소드를 사용하면 될 것이라고 생각했다. 하지만 통과되지 않았다. 그래서 문제를 다시 보니 제자리 알고리즘을 이용해서 해결하라는 것이다. 제자리 알고리즘이란?
filter 메소드를 사용하거나 새 배열을 만들어서 해결하는 것은 추가적인 저장 공간을 사용하는 것이기 때문에 제자리 알고리즘 방식이 아니다.
Custom Judge가 제자리 알고리즘을 이용해서 해결했는지 판별하는 것 같다.

제자리 알고리즘으로 해결하기 위해서는 2개의 포인터(Two Pointers)가 필요했다. 문제의 태그로 나와있는것처럼

• k 포인터는 val와 일치하지 않는 마지막 요소를 가리킨다.
• i포인터는 val와 일치 여부를 판별해야할 요소를 가리킨다.

for문으로 이용해서 val와 일치하지 않으면 k번째 인덱스에 해당 요소를 재할당하고 k를 1 증가시킨다. 즉, k포인터의 위치를 다음 인덱스로 옮긴 것이다.
이 과정을 마지막 요소까지 행하게 되면 k값이 나오게 된다.