[LeetCode] 80. Remove Duplicates from Sorted Array II

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150 

Remove Duplicates from Sorted Array II - LeetCode

문제 유형 : 배열

문제 난이도 : Easy

 

문제

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

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.

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

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

 

배열 nums에는 최대 2개의 중복된 요소가 들어있습니다. 2개를 초과하는 배열들은 지우고,

nums 배열에는 기존의 감소하지 않는 순서대로 하도록 합니다.

nums의 요소는 -10^4 부터 10^4의 범위 안의 숫자를 가집니다.

 

풀이

last_num변수를 만들어서 이전의 값을 저장해준다.

nums배열을 0-인덱스부터 순차적으로 탐색하다가, last_num과 curr_num이 같으면 카운트를 하나 올린다.

카운트가 3이 넘으면(요소가 3개 이상이면) 현재 숫자를 -1e9(범위 밖의 숫자)로 설정한다.

탐색이 끝나면, 요소들을 없애준다.

 

코드(C++)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int cnt = 1;
        int last_num;
        int curr_num = -1e9;
        for(int i = 0; i < nums.size(); i++){
            last_num = curr_num;
            curr_num = nums[i];
            if(last_num == curr_num){
                cnt++;
                if(cnt >= 3){
                    nums[i] = -1e9;
                    continue;
                }
            }
            else{
                cnt = 1;
            }
        }
        nums.erase(remove(nums.begin(), nums.end(), -1e9), nums.end());

        return nums.size();
    }
};