[Array/String] Remove Duplicates from Sorted Array

1. 문제

LeetCode - Remove Duplicates from Sorted Array
오름차순으로 정렬된 정수 배열 nums가 주어졌을 때, nums에서 중복 항목을 제자리에서 제거하고, nums에서 고유한 요소의 수를 반환하는 문제

2. 접근법

1. Remove Element와 비슷한 문제, 똑같이 ArrayList를 활용하는 방식으로 접근
2. ArrayList에 nums의 고유한 요소들만 담아준다.
3. 이후, nums의 앞에서부터 ArrayList의 사이즈 만큼 순회하면서 재배치하여 테스트 통과

3. 풀이

import java.util.ArrayList;

class Solution {
    public int removeDuplicates(int[] nums) {
        // 고유한 요소를 담기 위해 ArrayList 사용
        ArrayList<Integer> list = new ArrayList<>();

        // nums의 고유한 요소 수 k
        int k = 0;

        // nums를 전체 순회하면서 list에 없으면 list에 채워준다
        for (int n : nums) {
            if (!list.contains(n)) {
                list.add(n);
                k++;
            }
        }

        // nums 재배치
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }

        return k;
    }
}

4. 성능

- Runtime : 15ms -> 1ms(개선)

- Memory : 43.7mb

5. 개선

• Remove Element 문제의 개선 버전과 마찬가지로 two-pointer 접근법 사용하여 개선
• Runtime 1ms로 개선

class Solution {
    public int removeDuplicates(int[] nums) {
        // two-pointer 전략
        // k를 인덱스로 활용
        int k = 1;

        // 2번째 요소부터 nums 전체 순회
        for (int i = 1; i < nums.length; i++) {
            // 오름차순 정렬되어 있기 때문에 바로 이전 요소랑만 비교해주면 됨
            if (nums[i] != nums[i - 1]) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
}