LeetCode 80 - Remove Duplicates from Sorted Array 2

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii

 

오름차순으로 정렬된 nums가 주어졌을 때 중복된 요소를 제거해야 한다.

단 각각의 중복된 요소들은 최대 2개까지 유지된다. 요소들의 상대적 위치는 유지돼야 한다.

배열의 길이를 수정하는 것이 불가능하기 때문에 제거되지 않은 요소들을 앞에 위치시키고 제거된 요소들은 뒤에 위치시켜야 한다.

최종적으로 nums를 수정한 다음 유효한 숫자들의 개수를 반환해야 한다.

추가 공간을 사용해서는 안된다.

 

https://leetcode.com/problems/remove-duplicates-from-sorted-array

이 문제와 유사한 문제이지만 공간 조건이 추가됐고 중복 요소가 2개까지 유효하다는 조건이 추가됐다.

문제를 분석하고 구상해 보자.

1. 정렬이 된 상태이다. 즉 중복된 요소들은 인접해 있다.
2. 추가 공간을 사용할 수 없으므로 int [] nums 배열 내에서 조작을 해야 한다.
3. 중복 허용 횟수 조건이 생겼다. 최대 두 번까지 허용된다. → 관리가 필요하다.

어떤 방식들이 있을까

1. 카운터 현재 숫자의 출현 횟수를 세는 카운터를 두고 중복 횟수를 관리한다. → 이동이나 삭제는 어떻게 처리하지. 이 과정에서 비효율적일 수 있겠다.
2. 해시맵 혹은 해시 셋 추가 공간 사용이 불가능하다.
3. 투 포인터 배열을 순회하며 중복되지 않은 요소들을 배열의 앞부분에 모은다. 중복 허용 횟수 관리가 필요하다 → 이전 요소와 비교

따라서 투 포인터 방식을 채택한다.

두 개의 포인터를 둔다. s는 조건을 만족하는 유효한 숫자를 저장할 위치, p는 배열을 순회하는 포인터이다.

class Solution {
    public int removeDuplicates(int[] nums) {
        int s = 0;
        
        for (int p = 0; p < nums.length; p++) {
            if (s < 2 || nums[p] != nums[s - 2]) {
                nums[s] = nums[p];
                s++;
            } 
        }

        return s;
    }
}

큰 틀은 이전 문제와 유사하다. 이제 중요한 것은 중복 허용 횟수를 관리하는 방법이다.

우선 s가 2보다 작은 경우 즉 첫 두 개의 경우 무조건 조건을 만족하는 요소가 된다.

그 이후의 요소들을 검사해야 한다.

현재 위치(p)에서 앞의 두 요소와 현재 요소를 비교한다.

이때 nums [p]가 nums [s-2]와 다르다면 중복 횟수가 허용 범위 내라는 소리이다. 왜냐하면 nums[s-2]와 nums [s-1]이 이미 동일하다면 현재 요소까지 포함하면 중복이 3번이 되기 때문이다.