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

오늘의 Leetcode 난이도 easy 문제는 Remove Duplicates from Sorted Array 라는 문제입니다. 사실 이 문제를 풀까 말까 고민을 많이 했었는데요, 그 이유는 아래 [사진 1]과 같이, 역따봉이 따봉보다 3000점 이상 더 높았던 문제이기 때문입니다. Leetcode의 문제를 풀 때 조심해야 하는 부분이, 바로 역따봉이 많은 문제를 풀 때인데요, 이해할 수 없는 조건이 많이 부여되었거나 문제의 설명 및 예제를 이해하기 어려운 경우에 역따봉이 더 높아진다고 합니다. 우선 역따봉이 많은 오늘의 문제도 풀어보겠습니다.

 

 

Remove Duplicates from Sorted Array 문제 분석

 

<사진 1> Remove Duplicates from Sorted Array 문제

 

우선 [사진 1]의 문제에 대한 설명을 보겠습니다. 문제의 목표는 간단합니다. 주어진 integer 배열 nums를 오름차순으로 정렬할 때 중복되는 숫자들을 전부 제외시키고, 남아있는 숫자들의 총 개수를 반환하면 됩니다. 하지만 여기서 조심해야 하는 부분이, 입력받은 integer 배열의 크기가 바뀌거나, 또 다른 배열을 선언할 수 없다는 점입니다. 즉, nums 배열 내부에서 숫자들을 정렬시켜 나가야 합니다. 문제에서는 custom judge 라는 테스트 코드로 반환된 unique한 숫자 개수 k, k개 만큼 정렬된 nums 배열을 가지고 expectedNums라는 정답 배열과 element 레벨에서 하나씩 숫자를 비교합니다. For loop에서는 k 번만큼 진행됩니다. 

 

그러면 예제를 살펴볼까요? 첫번째 예제에서 nums는 [1, 1, 2]  배열이고, output은 k가 2, 최종 nums가 [1, 2, _ ]로 되어있습니다. 문제를 대충 읽었을 때는 underscore 문자가 무슨 의미인지 몰랐었는데요, 다시 문제를 읽어보니 여기에 어떤 수가 들어있어도 상관없다는 의미였습니다. 다음 예제도 살펴볼까요? 여기서 nums는 [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] 배열이고, output은 k가 5, 최종 nums는 [0, 1, 2, 3, 4, _ , _ , _ , _ , _ ] 입니다.

 

 

예제를 봤을 때 알 수 있는 사실은, nums의 0번째 index부터 (k-1)번째 index까지만 정렬된 unique한 숫자들만 배치된다면, 뒤에 나오는 수는 어떤 수든지 간에 신경쓰지 않아도 된다는 점입니다. 이 점을 이용해서 문제를 풀어보겠습니다.

 

 

Remove Duplicates from Sorted Array 문제 해결을 위한 C++ 코드

 

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int result = 0;
        
        if (nums.size() == 0)
            return result;

        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[result] != nums[i])
                result++;
            nums[result] = nums[i];
        }
        
        return result + 1;
        
    }
};

 

코드의 전체 목적은, nums에 unique한 숫자들이 등장할 때마다 nums의 result에 해당하는 index에 저장하는 것입니다. 우선 nums가 빈 배열이면 아무런 element도 저장되어 있지 않으므로, 0으로 초기화된 result를 그대로 반환합니다.

 

만약 빈 배열이 아니라면, nums의 1번째 index에 저장된 숫자와 0으로 초기화된 result에 해당하는 index의 숫자를 비교해서, 서로 다르면 result를 1씩 증가시킵니다. 만약 이 조건에 걸리지 않았다면 같은 숫자이기 때문에, result에 해당하는 index에 i 번째 숫자를 대입시킵니다. 이러면 중복된 숫자도 피하고, 중복이 아닌 unique한 숫자가 처음 등장할 때마다 result를 1씩 증가시킬 수 있습니다. 최종 반환값은 result + 1 입니다. 이는 result가 0으로 초기화되었기 때문입니다. 

 

 

Remove Duplicates from Sorted Array 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

<사진 2> Remove Duplicates from Sorted Array 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

그러면 다른 사람이 작성한 코드도 살펴보겠습니다. 이 분은 위 [사진 2]와 같이 2개의 솔루션 코드를 제시했습니다. 첫번째 솔루션은 제가 작성한 코드와 약간 비슷한 느낌이 드는 코드네요. 처음 조건문에서 2 미만의 element를 갖는 nums 배열이 들어왔다면 그대로 nums 배열의 크기를 반환합니다. 저는 nums 배열의 크기가 0인 경우에 대해서만 조건문을 작성했는데 이게 더 좋아보이네요. 이후에 loop을 돌면서 j 번째 index에 unique한 숫자들을 넣어주고, 최종 반환되는 값은 ans 변수를 두었습니다. 중복된 경우에 대해서는 skip을 하고 있습니다. 

 

두번째 솔루션을 살펴보겠습니다. 여기서는 set 을 사용해서 nums 배열의 값들 중 unique한 값들만 유지합니다. set을 사용하면 unique한 값들만 저장되는데요, 하지만 문제에서 extra space를 할당받지 말라는 조건이 있었기 때문에 아쉬운 부분이기도 합니다. 이후에 set에 저장된 모든 숫자들을 다시 nums 배열에 순차적으로 저장시키고 ans 변수를 반환합니다. 

 

지금까지 역따봉이 많았던 leetcode 난이도 easy 문제 중 하나였던 Remove Duplicates from Sorted Array에 대한 코드를 살펴보았습니다. 다음 시간에도 leetcode 문제로 또다시 찾아뵙겠습니다.