[Leetcode][C++][난이도 Easy] Remove Element

Leetcode의 난이도 easy 문제인 Remove Element의 문제 분석 및 C++ 풀이를 해보겠습니다. 이번에도 역따봉이 더 많은 문제인데요, 역따봉이 많은 문제는 풀이 방법만 알고 스킵해도 좋지 않나 생각합니다. C++ 기반 프로그래밍 실력을 향상시키고 싶거나, IT 기업의 코딩 테스트 준비를 위해 leetcode 이외의 다른 코딩 테스트 사이트도 알고 싶으신 분들은 바로 검색하는 것을 추천합니다.

 

 

Remove Element 문제 분석 

 

 

[사진 1] Remove Element 문제

 

지난 시간에 풀어봤던 Remove Duplicates from Sorted Array 문제와 비슷하게, nums 배열에 val이라는 integer 변수에 저장된 0 이상 100 이하의 값이 존재하면 이를 전부 제거하고, 제거되지 않고 nums에 남아있는 숫자의 개수를 반환하는 문제입니다. 지난 시간에 풀었던 문제를 참조하고 싶으시다면 아래 제 블로그의 글을 참조하셔도 좋습니다.

 

[Leetcode][C++][난이도 Easy] Remove Duplicates from Sorted Array

 

하지만 nums 배열에서 val에 해당하는 숫자들을 지우고 남은 자리에, 지워지지 않은 숫자들을 nums에 다시 재배치해서 index 0부터 채워넣어줘야 합니다. 이게 말로만 설명하면 어렵기 때문에, 예제를 보면서 설명 드리겠습니다. 첫번째 예제에서 nums는 [3, 2, 2, 3]이고, val은 3입니다. 그러면 nums에서 3을 지워주면 [ _ , 2, 2, _ ] 가 되겠네요. 이 상태에서 그냥 반환을 해버리면, custom judge 코드에서 index 0에 이상한 숫자가 들어있어서 오류를 출력하게 됩니다. 따라서, [2, 2, _, _  와 같이, 남아있는 숫자 2들을 nums 배열 안에서 재배치 해줘야 하고, 2가 2개만 남아있으니까 2를 return 합니다. 이 때, nums 대신 다른 배열에 이 값들을 넣어서 반환하면 안됩니다. Custom judge 코드가 nums 배열로 평가를 진행하기 때문이죠. Custom judge 코드가 없었다면 이 문제는 더 쉽게 풀렸을지도 모릅니다. 

 

 

다른 예제도 살펴보겠습니다. 여기서는 nums가 [0, 1, 2, 2, 3, 0, 4, 2] 이고, val이 2입니다. 따라서, nums에서 2가 전부 제거되기 때문에, [0, 1, 3, 0, 4]가 됩니다. 그리고 남은 숫자가의 개수가 5이기 때문에, 5가 return 됩니다. 이 때의 nums도 역시 2가 제외된 자리에 남아있는 숫자들이 앞으로 이동되어야 함을 알 수 있습니다. 그러면 나머지 빈 공간에는 무슨 숫자를 채워넣어야 할까에 대해 고민할 수도 있는데요, custom judge의 코드를 보면, index 0부터 return된 5 미만까지 for loop이 실행되는 것을 알 수 있습니다. 따라서 어떤 수를 채워 넣어도 상관없습니다.

 

코딩 테스트 문제 풀이와 관련하여 더 많은 정보를 얻고 싶으신 분들은 바로 인터넷에서 검색하는 것을 추천합니다.

 

 

Remove Element 문제 해결을 위한 C++ 코드

 

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

 

이제 제가 작성한 코드를 살펴보겠습니다. 우선 nums의 크기가 0이라면 아무런 숫자도 저장되어 있지 않으니까, 그대로 0을 반환했습니다. 만약 1이상의 크기를 가진 nums라면, nums의 크기만큼 loop을 돌면서, val과 일치하는지 안 하는지를 검사합니다.

 

만약 일치하지 않는다면, 0으로 초기화된 k번째 index에 현재 i번째 index의 nums의 숫자를 저장하고 k를 1씩 증가시킵니다. 결국 k가 하는 역할은 val이 아닌 숫자가 등장할 때마다 nums의 0번째부터 차례대로 숫자를 저장하기 위한 index의 역할을 수행합니다. 그리고 이 k를 반환해서, nums에 남아있는 숫자들의 총 개수를 반환합니다.

 

제가 작성한 C++ 코드 이외에 다른 프로그래밍 언어로 이 문제를 해결한 코드를 참고하고 싶으시다면, 역시 인터넷에서 추가로 검색하는 것을 추천합니다.

 

 

Remove Element 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

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

 

이제 다른 사람이 작성한 코드를 살펴보겠습니다. 저처럼 nums의 크기가 0일 때의 예외처리를 하지 않은 것을 제외하면 코드가 동일하네요!  j를 val이 아닌 숫자들의 총 개수 정보를 저장하기 위해 선언해줬고, nums의 크기만큼 loop을 돌면서 val과 일치하는지 안 하는지를 검사합니다.

 

그리고 nums의 j 번째 index부터 차례대로 val이 아닌 숫자들로 갱신시켜주고 그때마다 j 를 1씩 증가시키는 방향으로 업데이트를 합니다. 

 

지금까지 leetcode 난이도 easy의 문제 Remove Element를 C++로 풀어보는 시간을 가졌습니다. 다음에도 leetcode 난이도 easy 문제로 찾아뵙겠습니다. 다른 프로그래밍 언어로 이 문제를 해결한 코드 또는 이와 비슷한 코딩 테스트 문제도 인터넷에서 바로 검색해서 추가로 공부해보시는 것을 추천합니다.