[LeetCode] 26번 (Remove Duplicates Sorted Array 1)

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

Remove Duplicates from Sorted Array - LeetCode

---

🤣 문제 설명

• 오름차순 정렬된 정수 배열 nums 이 주어진다.
• 해당 배열의 중복된 숫자를 삭제한 후 남은 nums 의 크기를 반환한다.
• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100

 

🥲 문제 해결

• 역시나 새로운 배열을 생성하지 않고 투포인터 접근 방식으로 해결할 수 있다.
• nums 를 순환하면서 연속된 두 요소가 같지 않을 시 (중복된 값이 아닐 시), write 할 포인터 인덱스 값에, read 한 포인터 인덱스 값을 넣어주면 된다.
• write 할 인덱스의 크기가 곧 남은 nums 의 크기를 대변할 것이다.

 

😊  시간 복잡도

O(nums.length-1) 이지만, 최대 크기는 30000 이므로 충분하다.

 

🙂 공간 복잡도

정수형 변수 k 하나만 생성했기 때문에 O(1) 이다.

 

😉 정답

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

 

😌 개선사항

• 역시나 투포인터로 접근하니 쉽게 해결할 수 있었다.
• 코틀린 코드를 보니 splice 메서드를 통해 쉽게 배열을 자르고 관리하는걸 볼 수 있었다. 자바 타입에서는 이와 같은 방법을 사용할 수 없는지 뭐가 더 좋은 방식인지 더 문제를 풀어보면서 생각해봐야겠다.