[LeetCode] 26. Remove Duplicates from Sorted Array (1)

Problem

Remove Duplicates from Sorted Array

Background

• 비내림차순 정수 배열에서 중복 원소를 제거
• nums 의 고유 원소 개수를 k로 규정
• 중복을 제거한 후 고유한 요소 k의 개수 반환
• 반환된 k 외에 무엇을 남겨두는지는 중요하지 않음

Failed Solution

힌트

특이하게 int(정수형) 를 반환하지만, 제공된 정수형 배열 nums[] 안의 원소를 체크하는 문제다.

즉, 단순히 int 값을 올바르게 구하는 것이 끝이 아닌 문제이다.

• Set 을 통한 중복 원소를 제거하는 쉬운 방법은 통과할 수 없다.

하지만, 이전 two-pointer 문제와 같은 유형이라는 걸 알 수 있다.

바로, 고유한 원소를 남기고 순회하면서 중복된 원소일지 아닐지를 판별한인덱스를 설정하면 된다는 점에서 눈치챌 수 있다.

그래서, 다음과 같이 각 인덱스를 설정했다.

1. 비내림차순 정렬에서 고유한 원소를 식별할 인덱스: uniqueIndex
2. 배열을 순회할 인덱스: index

그리고, 결국 고유한 원소를 남기면 되므로 fail case 를 fast exception 처리를 하기 위해 같을 경우 skip 하도록 처리했다.

• 다를 경우는 우리가 찾는 고유한 원소이므로 uniqueIndex가 가리키는 원소에 값을 대입하도록 했다.

class Solution {
    public int removeDuplicates(int[] nums) {
        // 1. 비내림차순 정수 배열에서 고유한 원소를 식별한 인덱스
        int uniqueIndex = 0;

        // 2. 배열을 순회
        // (1) nums[index] 와 nums[uniqueIndex] 가 같을 경우, 다음으로 패스
        // (2) nums[index] 와 nums[uniqueIndex] 가 다를 경우, 
        // nums[uniqueIndex] = nums[index]
        for (int index = 0; index < nums.length; index ++) {
            if (nums[index] == nums[uniqueIndex]) continue;

            nums[uniqueIndex] = nums[index];
            uniqueIndex ++;
        }

        return uniqueIndex;
    }
}

오답인 이유

하지만, 위 풀이로 진행할 경우 다음과 같은 문제가 발생한다.

좌측에서부터 고유한 맨 첫 번째의 원소는 항상 다음으로 고유한 원소로 덧씌워진다.

즉, [1, 1, 2] 일 경우 우리는 [1, 2] 를 기대하지만 [2] 만 남게 된다.

결국, 위 방법으로 풀었을 때는 맨 첫 번째로 고유한 원소를 보호할 수 없게 된다는 문제가 있다.

key point

그럼 첫 번째로 고유한 원소를 보호할 수 있게 하려면 어떻게 할 수 있을까?

해당 원소 다음부터 순회하면 되지 않을까?