[LeetCode] Remove Duplicates from Sorted Array

문제 링크

Remove Duplicates from Sorted Array - LeetCode

Can you solve this real interview question? Remove Duplicates from Sorted Array - Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place [https://en.wikipedia.org/wiki/In-place_algorithm] such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums. Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things: * Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums. * Return k. Custom Judge: The judge will test your solution with the following code: int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length int k = removeDuplicates(nums); // Calls your implementation assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; } If all assertions pass, then your solution will be accepted. Example 1: Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores). Example 2: Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores). Constraints: * 1 <= nums.length <= 3 * 104 * -100 <= nums[i] <= 100 * nums is sorted in non-decreasing order.

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

문제 요구 조건

문제에서 요구하는 조건은 다음과 같다.

integer array 제공

감소하지 않는 배열로 제공 -> 뒷 값이 앞 값보다 작을 수 없다. ( non-decreasing )

중복되는 것을 제거

nums의 앞 부분의 요소들이 expected 배열과 같아야 한다. 그 뒤에는 상관없음

in-place -> 새로 배열을 만드는 것이 아니라, nums 배열 자체를 수정 (메모리 사용량 요구)

고유한 값들의 갯수를 숫자로 반환 -> k → 리턴값이 k

처음에 내가 시도한 방법

일단 먼저 토스 코딩테스트를 해봐도, javascript문서 정도는 읽을 수 있게 해주기 때문에 옆에 공식문서를 띄워놓고 문제를 풀었다. 결론적으로는 문제를 풀지 못했고, 스스로 정한 문제 풀이 시간 30분을 초과했다. 처음 내가 문제를 풀려고 했던 방법은 다음과 같다.

배열의 이전값과 다음값을 비교해서 undefined로 대입

-1 로 대입을 할려니 나중에 정렬이 되지 않아서 undefined로 대입했다. 나중에 필터링 해야겠단 생각이 있었기 때문이다.

sort함수 사용

자바스크립트 문서를 통해서 sort함수를 사용해서 정렬을 할려고 했다.

filter함수 사용

그리고 마지막으로 undefined 를 필터링해서 반환할려고 했지만, 문제를 약간 잘못 이해했기에 이 부분에서 좀 막혀있었다. 결론적으로는,

k값이 반환 되어야 했다.

nums는 따로 검증로직을 실행한다 ( nums를 반환할 필요가 없었다. )

나의 문제 풀이

JavaScript

var removeDuplicates = function (nums) {
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === nums[i + 1]) {
            nums[i] = undefined;
        }
    }

    nums.sort((a, b) => a - b)
    // nums.toSorted()

    console.log(nums)
    console.log(nums.length)
    nums.filter((num) => num !== undefined)

    return
    Object.keys(nums)
};

나의 문제풀이 피드백

nums[i] = undefined;

중복된 값을 undefined 로 바꾸는 것은 배열의 길이를 줄이지 않는다.

nums.sort((a, b) => a - b)

이 작업으로 배열의 모양이 [1, 2, 3, undefined, undefined]처럼 보일 수 있어 정답처럼 보일 수 있지만, 문제는 제자리 수정 (in-place)을 요구했다.

nums.filter(...)

filter 함수는 기존 배열을 수정하지 않는다. 요소를 모아서 새로운 배열을 만들어 내기 때문에 문제에서 요구하는 방법이 아니다.

문제 풀이

이 문제를 풀기 위해서는 two pointer 라는 개념이 필요한 문제였다. 설명하자면 하나의 포인터는 고유한 값이 들어갈 index를 가리키고, 다른 포인터는 배열을 순회하는 포인터로 사용하는 예제였다.

문제 풀이 코드

JavaScript

var removeDuplicates = function (nums) {
    // 배열이 비어있으면 0을 반환
    if (nums.length === 0) {
        return 0;
    }

    // insertIndex는 다음에 채워질 고유한 값의 위치를 가라칸다
    // 0번 인덱스는 이미 고유 값이므로 1부터 시작
    let insertIndex = 1;

    // 배열의 두 번째 요소(인덱스 1)부터 끝까지 순회
    for (let i = 1; i < nums.length; i++) {
        // 현재 요소가 이전 요소와 다른지 확인 (새로운 고유 값 발견!)
        if (nums[i] !== nums[i - 1]) {
            // 고유 값을 insertIndex 위치에 덮어쓴다
            nums[insertIndex] = nums[i];
            // 다음 고유 값이 들어갈 위치를 한 칸 뒤로 옮긴다
            insertIndex++;
        }
    }

    // 최종적으로 insertIndex의 값이 고유한 요소의 개수(k)가 된다
    return insertIndex;
};

insertIndex라는 고유값을 지칭하는 Index를 따로 관리한다.

최초값은 이미 고유한 값이기 때문에 index값을 1로 초기화

배열의 1번째 요소부터 끝까지 순회(i)한다

현재 값(nums[i])이 바로 이전 값(nums[i-1])과 다를 경우에만, 이 값을 nums[insertIndex] 위치에 덮어쓴 후 insertIndex를 1 증가시킨다.

루프가 끝나면 insertIndex의 값이 바로 고유한 요소의 개수(k)가 된다.

최고의 성능을 낸 문제풀이

JavaScript

var removeDuplicates = function(nums) {
    const set = [...new Set(nums)];
    for (let i = 0; i < set.length; i++) {
        nums[i] = set[i];
    }
    return set.length;
};

최고의 성능을 낸 풀이는 Set 이라는 자료구조를 활용해서 풀이한 방식이었다. 물론 엄청 간결하고 직관적이라서 가독성이 좋긴 하지만, 문제 요건중에 in-place의 의도를 정확하게 파악했다면, 메모리 사용량을 줄이기 위해서 다른 배열을 생각을 하지 않았을 것 같다.

만약 메모리의 추가공간없이 해결하라는 제약이 있었다면 감점요인이 될 수도 있다.