문제 푼 날짜 : 2021-11-24

문제

문제 링크 : https://leetcode.com/problems/remove-duplicates-from-sorted-array/

접근 및 풀이

문제를 읽자마자, 입력이 오름차순으로 정렬이 되어있었기 때문에 C++의 erase와 unique 함수를 이용하여 중복을 제거하면 된다고 생각했다.
정답이긴 했지만, 이렇게 풀라고 만든 문제가 아니라고 생각했다.
문제의 조건에서 'remove the duplicates in-place'인 점을 이용해서 주어진 vector 내에서 추가적인 공간을 사용하지 않고, C++ 라이브러리를 이용하지 않고 구현해보았다.

1. 임의의 index를 둔다.(1부터 시작)
2. vector의 맞닿은 원소끼리 비교해준다.
3. 비교한 두 값이 다를 경우 한 칸 뒤의 값을 index의 위치에 넣어준다.
4. 2, 3번을 모든 원소를 탐색할 때까지 반복해준다.
5. index 값이 중복되지 않은 원소의 갯수가 된다.

코드 (라이브러리 이용)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        return nums.size();
    }
};

코드 (다른 풀이)

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

결과

피드백

너무 라이브러리를 떠올리는게 익숙해져서 그런지 생각을 통해 구현하는 법을 잊은 것 같다.
항상 여러 방법으로 구현하는 연습을 해야겠다.