[leetCode] 27. Remove Element (Easy) 풀이

❓ 문제

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

 

정수 배열 nums와 정수 val이 주어지면 nums에서 val의 모든 항목을 제자리에서 제거합니다. 요소의 상대적 순서는 변경될 수 있습니다.

 

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

 

일부 언어에서는 배열의 길이를 변경할 수 없으므로 결과를 배열 nums의 첫 번째 부분에 배치해야 합니다. 더 공식적으로, 중복을 제거한 후 k 요소가 있는 경우 nums의 처음 k 요소가 최종 결과를 보유해야 합니다. 처음 k개 요소를 넘어 무엇을 남겨두는지는 중요하지 않습니다.

 

Return k after placing the final result in the first k slots of nums.

nums의 첫 번째 k 슬롯에 최종 결과를 배치한 후 k를 반환합니다.

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

 

다른 배열에 추가 공간을 할당하지 마십시오. O(1) 추가 메모리를 사용하여 제자리에서 입력 배열을 수정하여 이 작업을 수행해야 합니다.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

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).

 

설명: 함수는 nums의 처음 두 요소가 2인 k = 2를 반환해야 합니다.
반환된 k(따라서 밑줄임) 뒤에 무엇을 남겨두어도 상관 없습니다.

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).

 

설명: 함수는 0, 0, 1, 3, 4를 포함하는 숫자의 처음 5개 요소와 함께 k = 5를 반환해야 합니다.
5개의 요소는 임의의 순서로 반환될 수 있습니다.
반환된 k(따라서 밑줄임) 뒤에 무엇을 남겨두어도 상관 없습니다.

❗ 내 답변

/**
 * @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;
};

Runtime: 69 ms
Memory Usage: 42.2 MB

 

지난 포스팅과 동일한 방식으로 해결했다.

❗ Runtime이 가장 빨랐던 답변과 비교

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

Runtime: 91 ms
Memory Usage: 42.3 MB

 

통계차트에서 런타임이 가장 빠르게 나온 답변이라고 해서 가져왔는데 음..
역시 오늘도 릿 코드 통계 차트는 정확하지 않다^^;;

개인적으로 어차피 nums.length 가 0이면 아예 반복을 돌지 않고 그대로 0인 j를 반환할 텐데
굳이 if (!nums.length) return 0 을 써준 이유를 모르겠다.

nums.length만큼 반복을 돌면서 val와 값이 같지 않으면
j를 증가 시켜 다음값과 비교한다.
nums를 따로 자르거나 하진 않아 런타임이 빠르게 나온 것 같다.

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    var index = nums.indexOf(val);
    for(;;) {
        var index = nums.indexOf(val);
        if (index !== -1) {
              nums.splice(index, 1);
        } else {
            break;
        }
    }
};

Runtime: 83 ms
Memory Usage: 42.2 MB

 

나는 for(;;) 나 while(true) 이런식으로 적는 걸 선호하지 않는다.
무한 루프가 발생할 수도 있기 때문에...

아무튼 이 답변에선 반복을 돌면서 indexOf로 val과 일치하는 값의 인덱스를 찾아 splice해줬다.
ES6를 사용했다는 점에선 좋아보이지만 indexOf로 인해 내부적으로 반복을 여러번 돌게 되는 것 같아
RunTime이 빠른 답변 같진 않다.

💡 개선 방안

splice 같은 nums를 자르는 로직을 추가하지 않으면 런타임이 줄어드는 것 같다.