LeetCode: 26번 (Remove Duplicates from Sorted Array) [JAVA]

문제 링크

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Remove Duplicates from Sorted Array - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 nums 배열을 한 번 돌면서 전체 숫자 종류 파악
2. 그 다음 가장 맨 앞의 숫자를 두고 이를 temp에 저장한 다음, 그 이후를 while문으로 돌며 지정된 index(초기값 1) 위치에 넣을 숫자를 찾아 반복
   1) nums 배열을 하나씩 넘어가며 기존 temp에 저장된 숫자와 다른 숫자를 확인
   2) 이후 해당 다른 숫자와 index 위치에 있는 배열 숫자 간의 swap 진행
   3) temp를 현재 바꾼 숫자로 변경하고 index 값 하나 증가
   
3. 기존 카운트한 숫자 종류의 개수 반환

 문제에서 주어진 nums 배열의 경우 증가하는 순서로 정렬이 되어 있고, 중복되는 숫자들이 존재하는 형태이다. 이러한 상황에서 함수를 통해 nums 배열 속 앞 부분을 기존 중복되지 않는 숫자들로만 정렬되게 채워야 하는 상태인데, 이 경우 문제 요구 상 다른 배열을 생성하지 않고 O(1) 크기의 메모리 생성만이 허락된다. 결국 전체 배열을 돌며 숫자들을 따로 저장해놓을 수 없기 때문에 다른 방향을 사용해야 한다.

 우선 크게 nums 배열을 한 번 돌며 전체 숫자의 종류의 개수(k)를 계산한다. 그 다음엔 배열의 맨 앞 숫자를 temp에 저장하고 index를 1로 초기화한 다음 특정 과정을 반복하는데, 이는 순차적으로 nums 배열을 돌며 현재 temp와 다른 숫자가 등장할 경우 index 위치에 숫자와 해당 숫자를 swap 해주는 것이다. 이렇게 되면 swap이기 때문에 추가적인 메모리의 경우 하나의 int 자료형 하나만 존재하면 되고, swap 이후 temp를 현재 숫자로, index를 하나 증가 시켜 주며 다음 index 위치에 들어갈 다음 숫자를 찾는 과정을 반복하면 된다.

 

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }

        int k = 1, temp = nums[0], index = 1, i, swap;

        for (i = 1; i < nums.length; i++) {//전체 숫자 종류 파악
            if (temp != nums[i]) {
                k++;
                temp = nums[i];
            }
        }

        temp = nums[0];//첫 숫자
        i = 1;

        while (index < k) {
            if (temp < nums[i]) {//기존 temp와 다른 숫자라면
                //해당 숫자의 순서(index)와 swap 시도
                swap = nums[index];
                nums[index] = nums[i];
                nums[i] = swap;

                //temp 최신화
                temp = nums[index];
                ++index;
            }
            ++i;
        }

        return k;
    }
}

결과