Intuition 🤔

나는 전 문제인 Remove element에서 영감을 받은 답안을 적었다.
마찬가지로 fast pointer 하나와 slow pointer 하나로 duplicate 건너뛰기를 하며 duplicate이 아닌 element 들을 사용해 overwrite 하는 답안이다.

답안 1

class Solution {
    public int removeDuplicates(int[] nums) {
        int forwardIndex = 0; 
        int currentIndex = 0; 
        int currentElement = -101; 

        while (forwardIndex < nums.length) { 
            if (nums[forwardIndex] != currentElement) {
                nums[currentIndex] = nums[forwardIndex]; 
                currentElement = nums[forwardIndex];
                currentIndex++;
            }

            forwardIndex++; 
        }

        return currentIndex; 
    }
}

내 답안에서 currentIndex에 +1을 하지 않아도 되는 이유는 항상 overwrite를 한 후 한 칸만큼 앞으로 움직이기 때문에 항상 element의 개수와 같기 때문이다.

하지만 62%만큼의 효율성 밖에 달성하지 못했다. 그래서 다른 답안을 참고했다.

답안 2

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 0;
        for (int i = 1; i < nums.length; i++) {

            if (nums[j] != nums[i]) {
                j++;
                nums[j] = nums[i];
            }
        }
        return j+1;
    }
}

currentElement 가 곧 현재 slow pointer이 가리키고 있는 value이기 때문에, 새롭게 overwrite를 해야하는 상황에서는 인덱스를 앞으로 하나 움직여 거기에 overwrite한다.

currentIndex + 1을 하는 이유는 currentIndex는 항상 currentElement를 가리키고 있기 때문에 그 인덱스 +1을 해줘야 array length가 나오기 때문이다.

배운것

slow pointer로 currentElement를 표현할 수 있다면 그렇게 하자.
하지만 잘 모르겠다면 먼저 1번처럼 풀고 그 다음 생각해보는것도 방법.