5) LeetCode - Remove Element

https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150

---

나의 첫 코드는 이러했다.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count = nums.size();

        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] == val)
            {
                nums.erase(nums.begin() + i);
                count--;
                i--;
            }
        }
        return count;
    }
};

 

정답은 맞지만 해당 코드의 문제는 시간 복잡도.

O(N^2)를 사용하게 된다.

그 이유는 erase 함수.

 

  erase

erase 함수는 벡터의 원소를 삭제하는 것 까지는 좋지만 원소들을 하나씩 앞으로 당겨야하기 때문에 최악의 경우 O(N)의 복잡도를 가진다.

따라서 시간을 단축시키기 위해서는 새로운 벡터 변수를 가지고 위의 문제를 다루는 것이 좋다.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        vector<int> answer;
        int count = 0;
        
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] != val)
            {
                answer.push_back(nums[i]);
                count++;
            }
        }

        nums = answer;
        return count;
    }
};