[자료구조와 알고리즘] 80. Remove Duplicates from Sorted Array II

문제 설명

LeetCode TopInterview150 - 80. Remove Duplicates from Sorted Array II
정렬된 배열 nums가 주어지면 중복되는 값들을 제거한 다음 정렬된 상태로 nums를 변경하고
26번 문제와 비슷하지만 한번까지만 중복을 허용해서 그 갯수를 반환하는 문제로,
새로운 배열을 만들어서는 안되고 제자리 알고리즘을 사용해서 주어진 배열만 한번만 순회해서 해결해야 합니다.

풀어보기

26번 문제에서 알게된 더 좋은 코드를 활용해서 풀어봤습니다!
이번에는 isDuplicated의 Boolean 타입의 변수를 이용하여 중복된 숫자인지 아닌지를 확인해서 처리했습니다.

if (중복된 숫자가 아니면서 && 이전 숫자와 같다면) {
        배열에 추가;
        중복된 숫자 = true;
} else if (중복된 숫자가 아니면서 && 이전 숫자와 다르다면) {
        배열에 추가;
} else if (중복된 숫자면서 && 이전 숫자와 다르다면) {
        배열에 추가;
        중복된 숫자 = false;
}

var removeDuplicates = function(nums) {
    // 이전 숫자와 비교하기 위해서 1부터 시작합니다.
    let i = 1;                             
    let isDuplicated = false;
    for (let j=1; j<nums.length; j++) {
        if (!isDuplicated && nums[i-1] == nums[j]) {     // 
            nums[i++] = nums[j];
            isDuplicated = true;
        } else if (!isDuplicated && nums[i-1] != nums[j]) {
            nums[i++] = nums[j];
        } else if (isDuplicated && nums[i-1] != nums[j]) {
            nums[i++] = nums[j];
            isDuplicated = false;
        }
    }
    return i++;
};

좋은 코드

그런데 중복된 숫자인지 확인하기 위해 변수를 선언할 필요도 없이
현재 인덱스(k)에서 바로 앞의 숫자(k-1)와 그 앞의 숫자(k-2)를 확인해서 처리하는 좋은 코드를 발견했습니다.

var removeDuplicates = function(nums) {
    //  배열의 길이가 2보다 작다면 바로 반환
    if(nums.length <= 2) {
        return nums.length;
    }
    // 첫번째와 두번째 요소를 인덱스로 접근해야 하기 때문에 k는 2부터 시작합니다.
    // 그리고 첫번째와 두번째 요소의 값을 검증할 필요도 없습니다!
    let k = 2;
    for(let i = 2; i < nums.length; i++){
        // k-2 번째 숫자와 k-1 번째 숫자 중 다른 숫자가 나오기만 한다면 k번째에 추가해줍니다.
        if(nums[i] != nums[k - 2] || nums[i] != nums[k - 1]){
            nums[k] = nums[i];
            k++;
        }
    }
    return k;
};

하지만 의외로(?) 복잡도 면에서는 비슷했습니다.

마무리

문제를 풀어보기 전에 수도 코드로 미리 작성해보는 것이 더 간단하게 접근하는 데 도움이 많이 되는 것 같습니다.