[알고리즘] LeetCode - Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II - LeetCode

문제 설명

• 정수형 배열 nums가 오름차순 정렬되어 주어진다.
• 배열의 각 요소가 최대 두 번 나타나도록 일부 중복 항목을 제거한다.
• nums 배열에서 중복을 제거한 배열의 크기를 반환해야 한다.
• nums 배열에서 중복되는 수를 찾아 제거한 배열을 반환해야 한다.
• in-place 알고리즘을 사용하여 제거해야 한다.

문제 해결

• 이전 값과 현재 값이 동일한 경우에 nums 배열에 앞에서부터 차례대로 저장하고 중복 여부를 확인하는 dup 값을 true로 바꾼다.
• 이전에 중복된 수가 나온 경우에 nums 배열에 앞에서부터 차례대로 저장하고 중복 여부를 확인하는 dup 값을 false로 바꾼다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    public int removeDuplicates(int[] nums) {
        boolean dup = false;
        int prev = -1;
        int answer = 0;

        for (int i = 0; i < nums.length; i++) {
            if (!dup || prev != nums[i]) {
                nums[answer++] = nums[i];

                if (dup) {
                    dup = false;
                } else if (prev == nums[i]) {
                    dup = true;
                }
            }
            prev = nums[i];
        }

        return answer;
    }
}

결과

시간	메모리
1 ms	43.7 MB