[LeetCode/Easy] 26. Remove Duplicates from Sorted Array

1. Input

1) 오름차순으로 정렬된 int 배열 nums

 

2. Output

1) 중복이 제거된 후 남은 숫자들의 개수 k

2) 중복이 제거된 숫자들은 nums의 앞쪽에 배치시킴

3) 뒷쪽을 채울 값은 신경쓰지 않음

4) k를 정답 계산기에 넣고 답이 맞는지 확인할 예정

  - nums = {0, 0, 1, 2, 2}라고 한다면, 중복이 제거된 후에는 nums = {0, 1, 2, _, _}가 되므로 k = 3이 된다

  - 이를 정답 계산기에 넣었을 때, 0번째부터 k-1번째까지 nums[i] == answer[i]인지 확인

 

3. Constraint

1) nums를 복사해서 이용하는 등 메모리를 더 사용하는 것은 금지 (O(1) extra memory)

2) 1 <= nums.length <= 3 * 104

3) -100 <= nums[i] <= 100

 

4. Example

Input: nums = {1,1,2}
Output: 2

이때의 nums = {1,2,_}

 

5. Code

int k=nums.length-1;
for(int i=0 ; i<nums.length-1 ; i++){            
    if(i==k)
        break;
    if(nums[i]==nums[i+1]){
        for(int j=i+1 ; j<k ; j++){
            nums[j] = nums[j+1];
        } // for j
        k--;
    }// if
}// for i
return k+1;

  - 중복값이 확인될때마다 배열 값을 1칸씩 앞으로 땡기고, k값도 1씩 줄여나간다.

  - i == k가 되면 for문을 중단한다.

  - k는 중복을 없앤 값의 마지막 인덱스가 되므로, 1을 더해서 개수를 반환한다.

  - 느리다.

  - 중복값이 여러개가 연속되어있을 경우 한번에 없애지 못한다.