[Leetcode Top Interview 150] 80. Remove Duplicates from Sorted Array II

난이도 : medium

문제링크

• int array인 nums가 주어진다 (non-decreasing order)
• 중복 요소를 지워라 (in-place)
  • 두번까지 나타난 요소까지만 중복 표기 가능
• 순서를 유지하라

 

1. 접근법

• in-place 문제
  • 배열을 인덱스로 접근하여 풀기
• non-decreasing이며, 두개까지 중복허용이 가능하므로 투포인터를 사용하여 위치를 설정하기

 

2. 의사코드

int i=0;
while (left <= right && right < nums.length) {
	if (nums[left] == nums[right]) {
    	int tmp = right+1;
    	while (nums[right] == nums[tmp]) {
        	tmp++;
        }
        
        nums[i] = nums[left];
        nums[i+1] = nums[right];
        
        left = tmp;
        right = tmp+1;
    } else {
        nums[i] = nums[left];
    
        left++;
	    right++;    
    }
}

 

3. 구현 코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int ans = 0;
        int i = 0, left = 0, right = 1, tmp;
        int lVal, rVal;
        while (left < nums.length) {
            lVal = nums[left];
            if (left == nums.length-1) {
                nums[i] = lVal;
                ans++;
                break;
            }

            rVal = nums[right];

            if (lVal == rVal) {                
                tmp = right+1;                     
                while (tmp < nums.length && rVal == nums[tmp]) {
                    tmp++;
                }
                
                nums[i] = lVal;
                nums[i+1] = rVal;

                left = tmp;
                right = tmp+1;
                i += 2;
                ans += 2;
            } else {
                nums[i] = lVal;

                left++;
                right++;
                i++;
                ans++;
            }
        }

        return ans;
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 원소 순회함
• 공간복잡도 : O(1) - 상수 개의 변수만 선언됨 (반복문 내에서 메모리 할당 X)