/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
// nums 배열은 겹치는 값이 없도록 변경되어야한다.
for(let i = 1; i < nums.length; i++){
if(nums[i] === nums[i-1]){
nums.splice(i--, 1);
}
}
return nums.length;
};
in-place로 해결하기 위해서 추가적인 공간 할당 없이 해결했다.
인덱스를 1부터 시작하고, 이전 값과 비교하여 동일한 경우 해당 인덱스를 제거하는 것으로 진행했다.
여기서 추가 공간을 쓰지 않기 위해 splice()로 원본을 수정하며 진행했고,
제거 연산 후 빈 인덱스로 하나씩 밀려 들어오는 것을 고려하여
i--를 해줘 제자리에서 연산이 다시 진행되도록 했다.
다만 이 방법은 시간 복잡도가 상당히 높았다.
무려 19.1%의 기록이 나왔다.
어떻게 하면 시간 복잡도를 줄일 수 있을까?
var removeDuplicates = function(nums) {
let i = 0;
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== nums[i])
nums[++i] = nums[j];
}
return ++i;
};
two pointer 방법을 사용하신 것으로 보이는 분이다.
기준점을 i로 잡아놓고, j를 변경시키면서
두 인덱스의 값이 일치하지 않을 때, i에 j 값을 넣는 것이다.
이렇게하면 맨 앞에서부터 중복되지 않는 값들이 나열되며,
i번 인덱스까지의 배열이 중복을 제거한 배열이 되게 된다.
물론, 값을 제거하는 로직은 없기 때문에 i + 1번 인덱스부터 값이 여전히 존재한다는 점은 주의해야한다.