[LeetCode] 27. Remove Element

👿 문제 27. Remove Element

1. 정수 배열nums, 정수 val
2. nums에서 val을 전부 삭제하기
3. 삭제된 최종 nums를 return

😈 풀이

✔️ 첫번째 풀이

var removeElement = function(nums, val) {
    const newNums = nums.slice()
    nums.splice(0, nums.length)
    
    newNums.filter((el) => {
        if(el !== val){
            nums.push(el)
        }
    })
};

1. nums를 복사한다.
2. nums 내부 요소를 전부 삭제한다.
3. 복사한 배열에서 필터를 통해 nums에 push한다.

   시간 복잡도 : O(n)
   공간 복잡도 : O(n)

✔️ 두번째 풀이

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

1. nums를 순회하면서 val이랑 같은 요소가 있다면 배열에서 삭제한 후 인덱스를 하나 빼준다.

   시간 복잡도 : O(n^2)
   공간 복잡도 : O(1)

두번째 풀이에서 Runtime을 6ms, Memory를 0.05MB 줄일 수 있었다!
시간복잡도가 O(n)인 첫번째 풀이는 입력 크기에 비례하여 선형적으로 증가하는 반면, 시간복잡도가 O(n^2)인 두번째 코드는 입력 크기의 제곱에 비례하여 증가한다. 따라서 O(n^2)은 입력 크기가 증가할수록 더 빠르게 실행될 것으로 예상!

✅ 1일1알