[Array / String] Remove Duplicates from Sorted Array II

80. Remove Duplicates from Sorted Array II

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  const dupTwiceChkObj = {};

  for(let i = 0; i < nums.length; i++) {
    const num = nums[i];

    if(!dupTwiceChkObj[num]) {
      dupTwiceChkObj[num] = 0;
    }

    if(dupTwiceChkObj[num] === 2) {
      nums.splice(i, 1);
      i -= 1;
    }else{
      dupTwiceChkObj[num] += 1;
    }
  }

  return nums.length;
};

중복된 요소 개수를 체크할 해시테이블을 이용하였습니다. nums 배열의 요소에 변경을 가한 뒤, 탐색 기준이 되는 인덱스를 재조정하는 로직은 지난 문제 회고 게시글 [Array / String] Remove Duplicates from Sorted Array 에서 재사용하였습니다.

2. 해답을 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

Using two pointers

해답의 전문은 링크를 확인해주세요.

const removeDuplicates = function (nums) {
  if (!nums.length) return 0;

  let k = 0;

  for (let i = 0; i < nums.length; i++) {
    if (k < 2 || nums[i] > nums[k - 2]) {
      nums[k] = nums[i];
      k++;
    }
  }

  return k;
};

첫째, 필자의 해답(O(n))과 달리 공간복잡도에서 나은 성능을 보인 해답(O(1))입니다.

둘째, 채점 시스템을 활용하였습니다. Example 2에서 nums의 Output은 Expected와 다르지만, 채점 시스템은 k만큼의 요소만 검사하니 해답이 됩니다.

Output		: [0,0,1,1,2,3,3,3,3]
Expected	: [0,0,1,1,2,3,3]