[Leetcode] 80. Remove Duplicates from Sorted Array II - JS

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
- 오름차순 정렬된 정수 배열 nums
- 제자리에서 중복된 요소를 제거하라
- 단, 최대 2번까진 중복이 가능하다.
    - 결과값으로 나온 nums 배열의 요소 갯수(k)를 반환하라.
- 상대적인 순서는 유지한다.
- nums 배열의 길이는 변하지 않는다.
- 다른 배열에 추가 공간을 사용하지 말라. 공간 복잡도: O(1)

제한사항
--------------------
- 1 <= nums.length <= 3*10^4
- -10^4 <= nums[i] <= 10^4
- nums는 오름차순 정렬

 

 

2. 접근 방법

해쉬 테이블 사용
--------------------
포인터(k)와 해쉬 테이블(hash)을 만들어서 요소와 등장 횟수를 저장한다.
순회를 하면서 해쉬 테이블을 참조하여 2번 이하 등장했으면 
포인터에 현재 요소값을 할당하고 포인터를 이동 시킨다.

해쉬테이블 생성하면서 nums 배열도 수정하는 로직을 하나의 반복문에서 수행하니
첫번째 요소 일 때에는 포인터(k)를 이동시키지 않도록 조건을 추가했다.

 

 

풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
     const hash = {};
     let k = 1;
     for (let i = 0; i < nums.length; i++) {
        let elem = nums[i];
        if (hash[elem]) {
            hash[elem] += 1;
        } else {
            hash[elem] = 1
        }

        if (i !== 0 && hash[elem] <= 2) {
            nums[k] = elem;
            k++;
        }
     }
     return k;
};

 

위 풀이의 복잡도는 다음과 같다.

 

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

다른 사람 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let c=0 ;
    
    for(let i=0 ; i<nums.length ; i++){
        if(nums[i] !== nums[i+2]){
            nums[c] = nums[i];
            c++
        }
    }
    return c;
};

 

현재 위치와 2칸 뒤의 위치 값을 비교하여 값이 다르면,

포인터(c) 위치에 현재 값을 할당하고 포인터를 이동시킨다.

 

문제에서 최대 2개까지 중복을 허용하니 현재 위치 값과 두칸 뒤의 값을 비교한 뒤,

현재 값을 포인터에 할당 시켜주면 된다.

 

이러한 방법은 단번에 떠오르지 않는 것 같다. 다른 사람의 풀이도 자주 참고하면서 생각을 넓혀가자.