[leetCode] 26. Remove Duplicates from Sorted Array (Easy) 풀이

❓ 문제

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

 

내림차순으로 정렬된 정수 배열 nums가 주어지면 각 고유 요소가 한 번만 나타나도록 중복을 제자리에서 제거합니다. 요소의 상대적 순서는 동일하게 유지되어야 합니다.

 

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

 

일부 언어에서는 배열의 길이를 변경하는 것이 불가능하기 때문에 대신 배열 nums의 첫 번째 부분에 결과를 배치해야 합니다. 더 공식적으로, 중복을 제거한 후 k 요소가 있는 경우 nums의 처음 k 요소가 최종 결과를 보유해야 합니다. 처음 k개 요소를 넘어 무엇을 남겨두는지는 중요하지 않습니다.

 

Return k after placing the final result in the first k slots of nums.

 

nums의 처음 k 슬롯에 최종 결과를 배치한 후 k를 반환합니다.

 

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

 

다른 어레이에 추가 공간을 할당하지 마십시오. O(1) 추가 메모리를 사용하여 제자리에서 입력 배열을 수정하여 이 작업을 수행해야 합니다.

 

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).

❗ 내 답변

영어 지문 해석하는 게 왜 이렇게 어려운 지 모르겠다.
문제는 쉬웠는데 영어 지문 해석하는 데에서 오래 걸렸다 ^^;;

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

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === nums[i+1]) {
            nums.splice(i, 1);
            i--;
        }

    }

    return nums.length;
};

Runtime: 148 ms
Memory Usage: 45.2 MB

 

반복을 돌면서 현재 값(nums[i])과 바로 다음 값(nums[i+1])을 비교하고 같다면
해당 요소를 잘라낸다.
index는 그대로 증가 중인데 잘라낸 배열을 반복돌게되면 건너뛰는 요소가 발생하기 때문에,
잘라낸 요소 만큼 i를 감소 시켰다.

❗ Runtime이 가장 빨랐던 답변과 비교

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

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

Runtime: 136 ms
Memory Usage: 45 MB

 

start라는 인덱스 값을 0이라고 주고 반복을 돌린다.
nums[0]번째 값이 nums의 각 값들과 같지 않다면 start를 증가 시키고
증가시킨 값이 nums[i]가 된다.
nums[start] = nums[i]를 해 주는 이유는 i가 이미 증가되고 있는 상태이기 때문에 현재까지 비교한 위치에서 이어 비교하기 위함이다.

 

예) [1, 1, 2]

start	nums[start]	i	nums[i]	nums
0	1	0	1	[1, 1, 2]
0	1	1	1	[1, 1, 2]
0	1	2	2	[1, 1, 2]

마지막에 nums[start] 와 nums[i]의 값이 달라 start가 증가되어 값이 1이되고,
그 결과에 1을 더한 값을 반환하여
최종 반환값은 2이다. (서로 같지 않은 요소의 수)

즉, 서로 같지 않을 때 start를 증가 시키고, start가 0부터 시작했기 때문에
start 요소를 포함시키기 위해 반환 전에 1을 증가 시킨다.

nums를 잘라내거나 하지 않아 나보다 런타임이 더 빨랐던 것 같다.

❗ Memory 사용이 가장 적었던 답변과 비교

function min(a,b){
    return a > b ? b : a;
}
/**
 * @param {number[]} a
 * @return {number}
 * O(n*n)
 */
function removeDuplicates(a) {
    let uI = 1;
    let i = 1;
    while (i < a.length) {
        if (a[i] !== a[i - 1]) {
            a[uI] = a[i];
            uI += 1;
        }

        i += 1;
    }
    return uI;
}

Runtime: 117 ms
Memory Usage: 44.7 MB

 

런타임이 통계상 런타임이 가장 빨랐던 답변 보다 더 빠르게 기록되어 있다...
릿 코드의 통계 그래프가 명확하지 않은듯.

for문을 while로 썼을 뿐
RunTime이 빨랐던 답변과 거의 동일하다.
다른 점은 0이 아닌 1부터 시작했다는 정도?

💡 개선 방안

굳이 nums를 비워도 되지 않다면 splice 하지 않고 개수만 세는 것이 훨씬 RunTime이 빨리 나오는 방법인 듯 하다.
그리고 for 보다는 while을 쓰는 것이 RunTime을 빠르게 하는 방법인 것 같다.