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

문제정리

• Remove Duplicates from Sorted Array I과 메커니즘은 동일하지만 중복을 1회 허용하는 문제입니다.
• {1, 1, 1, 2, 3, 3, 3, 3}이 있다면 결과는 {1, 1, 2, 3, 3}이 됩니다.

풀이

1차 아이디어

• 이미 중복된 전적이 있는지를 체크하는 flag가 필요합니다.

첫 번째 중복 발견

• 첫 번째 중복을 발견한 시점에서는 alreadyDuplicated = false로 설정되어 있기 때문에 중복을 허용합니다. 그리고 두 가지 과정을 수행합니다.
  • 다음 중복부터 허용을 하지 않기 위해 alreadyDuplicated = true로 변경합니다.
  • 탐색된 값을 입력 Index 위치에 덮어씌운 후 탐색, 입력 Index 모두 +1씩 이동합니다.
    
    
    
    

두 번째 ~ 중복 발견

• 두 번째 중복을 발견한 시점에서는 alreadyDuplicated = true 입니다. 이때부터는 중복을 허용하지 않기 때문에 탐색 Index만 +1로 이동합니다.
  
  
  
  

새로운 값 발견

• 새로운 값을 발견한 순간입니다. 다음 과정을 수행합니다.
  • alreadyDuplicated = false 로 변경.
  • beforeValue 최신화.
  • 탐색된 값을 입력 Index 위치에 덮어씌운 후 탐색, 입력 Index 모두 +1씩 이동.
    
    

위의 과정들을 탐색 Index가 nums의 끝까지 도달할 때 까지 반복합니다.

코드

class Solution {

    public int removeDuplicates(int[] nums) {
        boolean alreadyDuplicated = false;
        int beforeValue = -1;
        int inputIndex = 0;

        for (int searchIndex = 0; searchIndex < nums.length; searchIndex++) {
            if (!isDuplicated(beforeValue, nums[searchIndex])) {
                alreadyDuplicated = false;
                beforeValue = nums[searchIndex];
                nums[inputIndex++] = beforeValue;
                continue;
            }

            // 중복인 경우
            if (!alreadyDuplicated) {
                alreadyDuplicated = true;
                nums[inputIndex++] = beforeValue;
            }
        }

        return inputIndex;
    }

    private boolean isDuplicated(int beforeValue, int nums) {
        return nums == beforeValue;
    }
}

2차 아이디어

1. index = 1 까지는 고려할 필요가 없다.

• 사실 중복을 한번 허용하기 때문에 index = 1 까지는 탐색할 필요가 없습니다.
• 그렇기 때문에 탐색, 입력 index를 2부터 설정해 시작하면 됩니다.
  
  
  
  

2. 사실 중복 플래그가 필요하지는 않다.

현재 문제에서는 1회 중복을 허용합니다. 그렇다는 말은 index - 2 와 중복만 아니면 조건을 만족할 수 있다는 것이죠. 결국 중복 플래그가 필요하지 않다는 것이죠.

코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int length = nums.length;

        if (length <= 2) {
            return length;
        }

        int inputIndex = 2;

        for (int searchIndex = 2; searchIndex < length; searchIndex++) {
            if (nums[searchIndex] != nums[searchIndex - 2]) {
                nums[inputIndex] = nums[searchIndex];
                inputIndex++;
            }
        }

        return inputIndex;
    }
}