[LeetCode] Remove Duplicates from Sorted Array - Javascript

Remove Duplicates from Sorted Array

[정렬된 배열에서 중복되는 값 제거]

 

 

제약 조건 

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];
}

Example

ex1) Input: nums = [1,1,2]
     Output: 2, nums = [1,2,_]

ex2) Input: nums = [0,0,1,1,1,2,2,3,3,4]
     Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

초기 문제 접근 방식

nums 배열에 있는 값들을 중복 제거하면 문제가 풀리겠다고 생각했다.자바스크립트의 filter와 indexOf를 사용해 중복제거를 할 수있다.

 

indexOf(): 배열에서 특정 값이 처음으로 나타나는 index를 리턴
filter(el, index, arr): 특정 조건에 부합하는 배열의 모든 값을 배열 형태로 리턴

el: 요소값

index: arr에서 요소의 index 값

arr: 순회하는 대상

초기 전체코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
   nums = nums.filter((el, index, arr) => {
      return arr.indexOf(el) === index;
   });
   console.log(nums);
   return nums.length;
};

다시 생각 해보며..

분명 case1, 2 모두 Stdout은 올바르게 출력이 되는데 Output은 중복제거된 배열로 출력되지 않았다.

remove the duplicates in-place such that each unique element appears only once.
letcode에서 문제를 처음 풀어봐 익숙지 않았던 문제가 있었는데, 바로 "in-place"다.
nums 배열은 아마 call by ref로 넘어와 주어진 nums 배열에서 처리해야 한다.

생각해 보니 이전 문제들에서도 "in-place"가 있었는데,

별도의 변수를 생성해서 문제를 푼 게 아닌 바로 splice 같은 것을 했기 때문에 풀렸다.
filter는 새 배열로 반환해 주기 때문에 nums 배열이 새로 만들어져 계속 문제 풀이에 실패했던 것 같다.

그렇기에 이번 문제에선 filter 메서드를 사용하지 않고 nums에 일일이 접근해 중복제거를 하여 풀어야겠다고 생각했다.

 

solve 전체 코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
   let tmp = nums[0];
   for (let i = 1; i <= nums.length; i++) {
      if (nums[i] === tmp) {
         nums.splice(i, 1);
         i--;
      }
      tmp = nums[i];
   }
   return nums.length;
};

tmp 변수를 생성해 해당 변수에 첫 번째 값만 초기화해주고, 반복문을 사용해 뒤에 있는 값과 비교해 값이 같은지 비교했다.

그 후 값이 같다면 splice로 해당 배열을 삭제하고 tmp 값을 계속 변경해 주며 비교했다.

nums 배열은 정렬된 상태로 오기 때문에 배열 인덱스의 바로 뒤의 값과 비교해도 문제없다.

다른 sovle 코드

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

   for (let i = 0; i < nums.length; i++) {
      if (nums[tmp] !== nums[i]) {
         tmp++;
         nums[tmp] = nums[i];
      }
   }
   return tmp + 1;
};

위의 방식으로 splice를 사용하지 않고 풀이가 가능하다.

tmp 변수를 0으로 초기화하고 반복문에 nums[tmp] 값과 nums[i]를 비교 해

값이 같지 않다면 tmp를 증가시키고 증가 한 값을 nums[i]에 넣는다.