Leet Code - 26. Remove Duplicates from Sorted Array(C++)

포타토·2019년 12월 18일

알고리즘

목록 보기

6/76

예제: Remove Duplicates from Sorted Array

문제
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

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

Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
풀이

영어!!!!!! 문제를 이해하는데 어려웠다. return value가 int인데, 결과는 array라니!

위에서 차분히 보면, 우선 중복된 수를 제거한 array의 length를 반환하란다.
즉, [0, 0, 1] -> [0, 1] 이면 2를 반환하라는 것이다.

여기서, 메모리를 많이 사용하면 안된다고 한다. O(1) extra memory를 사용하라는걸 보니, 하라는걸 보니... 영어를 잘 모르겠다😂. 구글링 해 보니, O(1) 메모리라는게 입력한 데이터 만큼의 메모리를 사용하라는 것이란다. 즉, 입력한 nums 벡터만큼의 추가 메모리를 사용할 수 있다는 뜻이 되겠다.

영어 독해를 피하려면 추가 메모리를 쓰지 않는것이 현명하다는 생각이 바로 들어버렸다.

또한, 블라블라 말이 많은데,

for (int i = 0; i < len; i++) {
    print(nums[i]);
}

이 for문을 봐서는 우리가 return한 len까지 nums를 print 하겠다는 것이다. 이래서 array 형태의 output이 나왔던 것이다. 더군다나 vector& nums, 즉 reference를 사용한다. 그말인 즉슨, nums vector를 물고 뜯고 씹고 변형하라는 뜻이다. 레퍼런스와 포인터.. 너무 어렵다.

아무튼, [0, 0, 0, 2] array가 들어온다면, [0, 2]를 만들던, [0, 2, 0, 0]을 만들던, 0, 2, 100, 1000을 만들던 앞에 [0, 2]가 오도록 변경한 후 2를 리턴하면 된다.

푸는 방법은 수없이 많겠지만, 필자는 nums 사이즈 만큼의 for문을 돌면서 중복되지 않는 값만 앞에서 채워주었다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int size = nums.size();
        if(!size) return 0;
        
        int num = nums[0];
        int idx = 1;
        for(int i = 1; i < size; i++){
            if(nums[i] != num){
                nums[idx] = num = nums[i];
                idx++;
            }
        }
        
        return idx;
    }
};