LeetCode 26 - Remove Duplicates from Sorted Array

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

 

중복되는 숫자를 제거하는 문제이다. int[] nums 배열 자체를 수정해야 한다.

nums는 오름차순으로 정렬 돼 있는 상태로 주어진다.

각 원소들의 상대적 위치는 유지 돼야 한다. 이때 nums 배열의 유니크한 원소의 개수(k)를 리턴하면 된다.

예시를 보자. int[] nums = [1, 1, 2] 일 경우 1 이 중복된다. 따라서 nums = [1, 2, _ ]로 변경되고 k는 2가 된다.

int[] nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] → [0, 1, 2, 3, 4, _, _, _, _, _ ] 이렇게 되고 k는 5가 된다. 기존의 상대적인 순서를 유지한다는 특징이 있다.

구상을 해보자.

1. 정렬이 돼 있다는 것은 중복이 존재하는 경우 연속으로 나온다는 뜻이다.
2. 배열 자체를 수정하기 때문에 요소를 제거하는 것이 아니라 유효한 요소들을 앞으로 모으는 작업이 필요하다.
3. 추가적인 자료구조는 사용할 수 없다. 주어진 int[] nums를 사용해야 한다.

가장 먼저 떠오르는 방법은 중복 요소가 발견되면 가장 뒤로 밀어내는 것이다. 하지만 이 방식은 O(N^2)의 시간복잡도로 매우 비효율적인 알고리즘이 된다.

배열을 순회하면서 교환이 필요하다. 이를 위해 두 개의 포인터를 사용하기로 했다. 즉 투포인터이다.

하나의 포인터는 중복되지 않은 요소의 위치를 가리키고 다른 하나는 배열을 순회하면서 중복을 검사한다.

정렬이 돼 있다 즉 인접한 요소만 보면 중복 검사가 가능하다.

class Solution {
    public int removeDuplicates(int[] nums) {
        int p1 = 0;
        
        for (int p2 = 1; p2 < nums.length; p2++) {
            if (nums[p1] != nums[p2]) {
                p1++;
                nums[p1] = nums[p2];
            }
        }

        return p1 + 1;
    }
}

p1은 유효한 숫자들이 자리 잡을 포인터이다.

p2는 이제 중복이 나오는 지를 확인하고 해당 값의 위치를 이동 시키기 위한 포인터이다.

이 알고리즘은 중복된 숫자가 나오면 마지막 중복 위치를 찾고 지금까지 유효한 위치 다음 위치에 해당 값을 대입하는 동작을 수행한다.

이를 통해 O(N)의 시간복잡도로 문제를 해결할 수 있었다.