[LeetCode] 80번 (Remove Duplicates Sorted Array 2)

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

Remove Duplicates from Sorted Array II - LeetCode

---

🤣 문제 설명

• 오름차순 정렬된 정수 배열 nums 이 주어진다
• 배열의 각 요소(숫자)의 중복 허용을 하나로 지정하고, 하나를 초과한 나머지 요소는 삭제한 후 남은 nums 의 크기를 반환한다.
• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104

 

🥲 문제 해결

• 투포인터 접근 방식으로 중복 수를 세는 count 변수 하나가 더 필요하다.
• nums 를 순환하면서 크게 두가지로 분기한다. 첫 번째로는 연속된 두 수가 같지 않을 때다. 이 때에는 중복 카운트 변수를 0으로 초기화 한 후, write 할 포인터 인덱스 값에 read 할 포인터 인덱스 값을 넣어주면 된다.
• 두 번째로는 연속된 두 수가 같을 때이다. 중복 하나는 허용하기 때문에 만약 count 의 값이 0 이라면, 마찬가지로 write 할 포인터 인덱스 값에 read 할 포인터 인덱스 값을 넣어준 후 count ++ 해주면 된다.
• 만약 count 값이 0 이 아니라면, 이는 중복 수를 초과했다는 뜻이므로, write 할 인덱스 k의 자리를 늘리면 안된다. 그래야 중복이 끝난 후의 read 한 값이 해당 자리수에 들어가게 된다.

 

😊 시간복잡도

O(nums.length-1)이다. 최대의 크기가 30000 이므로 문제없다.

 

🙂 공간복잡도

정수형 변수들만 선언했기 때문에 O(1)이다.

 

😉 정답

class Solution {
    public int removeDuplicates(int[] nums) {
        int count = 0;
        int k = 1;
        for(int i = 0; i<nums.length-1; i++) {
            if(nums[i]!=nums[i+1]) {
                count = 0;
                nums[k] = nums[i+1];
                k++;
            } else {
                if(count == 0) {
                    count++;
                    nums[k] = nums[i+1];
                    k++;
                }
            } 
        }
        return k;
    }
}

 

🙃 개선사항

• 구글링을 진행해보니, 두 조건으로 분기하지 않고 or 메서드를 통해 nums[i] 와 nums[i-2] 를 비교해 같지 않다면 즉 허용된 중복 수를 초과하지 않는다면 read, write 하는 코드도 많이 보였다.
• 코드의 가시성은 조금 좋아진 것 같지만 성능상 크게 다른 점은 없는 것 같아 아직은 신경쓰지 않아도 될 것 같다.