[Java Script]LeetCode 80. Remove Duplicates from Sorted Array II

1. 문제 개요

문제 링크 : 80. Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II - LeetCode

• 주어지는 1개의 배열(nums)에서 원자의 값을 2개씩 남겨두고 제거하시오

2. 문제 풀이

배열 내에서 중복값을 각 원자값별로 2개씩 남겨두고 제거하면 되는 문제

2개씩 원자값을 남겨야 하기에 중복을 허용하지 않는 자료구조로의 변환 방법은 사용할 수 없고 배열을 탐색하며

직접 제거하는 방식을 택했습니다.

 

이를 구현하기 위해 주석으로 코드의 구조를 잡아보면 다음과 같다.

var removeDuplicates = function(nums) {
	// 기존의 배열을 정렬하여 중복값끼리 인접하게 위치하도록 변경
    // 배열을 순서대로 탐색하면서 전후값이 같은지 체크
    // flag변수를 이용하여 중복값이 3개가 넘어갈 경우 해당 배열의 원자값을 제거
    // 인접한 값이 다른 값으로 변경되면 flag를 초기화
}

LeetCode 요구 양식으로 코드 구현

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    nums.sort(function (a, b) { return a - b });
    let before, flag = 0;
    for(i=0; i < nums.length; i ++){
        if(i == 0) before = nums[i]
        else{            
            if(before == nums[i]){
                flag++;                
                if(flag > 1) { 
                    nums.splice(i, 1) 
                    i--;
                } 
            }else flag = 0;
            before = nums[i]            
        }
    }
    return nums.length  
};

 

LeetCode 제출 결과

 

3. 시간 복잡도 계산

O(n) + O(n) = O(2n) => O(n) 

 

4. 개선 사항

배열을 정렬하는 과정에서 1차적인 1차적으로 메모리 및 시간 소모가 발생하였습니다.
정렬하지 않고 탐색하는 방법을 이용했다면 좀 더 효율이 높아질 것으로 보입니다.

 

5. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.