[ Top Interview 150 ] 80. Remove Duplicates from Sorted Array II

문제

80. Remove Duplicates from Sorted Array II

  Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

  Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

  Return k after placing the final result in the first k slots of nums.

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

• Input : 중복이 존재하는 오름차순으로 정렬된 배열 제공
• Output : 제공된 배열을 맨 앞부터 채워서 중복이 2개까지만 허용된 오름차순 배열로 변형
  • 최종적으로 정렬된 원소의 개수를 return
• 알고리즘 조건 : 다른 array 할당 금지, 입력받은 array와 O(1) 추가 메모리만 허용
  • 새로운 배열을 만들 수 없다.

문제 풀이 전략

• 이전 문제 26. Remove Duplicates from Sorted Array의 문제 풀이 전략을 이용함
• 선별이 완료된 원소의 위치를 가리키는 answerIndex를 1로 설정
• nums를 순회하면서 answerIndex에 있는 원소보다 크거나 같고, answerIndex에 한칸 전에 있는 원소보다 큰 경우
  • 해당 원소를 선별이 완료된 원소 위치로 이동함

1차 작성

class Solution {
    public int removeDuplicates(int[] nums) {
        int answerIndex = 1;

        for (int index = 2; index < nums.length; index++) {
            if (nums[answerIndex-1] < nums[index] && nums[answerIndex] <= nums[index]) {
                answerIndex++;
                nums[answerIndex] = nums[index];
            }
        }

        return answerIndex + 1;
    }
}

나의 문제 풀이 포인트

• 탐색이 완료된 부분에서는 어떠한 변형을 가해도 상관 없다는 것이 문제 포인트