Leetcode - 26. Remove Duplicates from Sorted Array - Easy

오늘의 문제는 정렬된 int 배열에서 겹친 숫자를 제외한 숫자는 몇개 인지 알아내는 문제 입니다.

문제에서 조건은 새로운 배열을 만들어서 풀지 말고 입력된 배열을 그냥 수정해서 답을 구하라는 겁니다.

 

예제를 보면 첫번째 배열 1,1,2 의 경우 2를 리턴 해야 합니다. 왜냐하면 중복된 숫자를 제외한 값은 1과 2 두 개 이기 때문입니다.

두번째 예제는 중복 된 값을 제외하면 남는 숫자들은  0,1,2,3,4 입니다. 정답은 5가 됩니다.

 

그럼 이제 패턴을 생각해 보겠습니다. (두번째 예제의 입력값을 보겠습니다.)

 

입력값은 일단 오름차순으로 정렬 돼 있습니다.

그러니까 첫번째 숫자는 제일 작은 숫자입니다. (0)

두번째 숫자를 첫번째 숫자와 비교해서 같은 숫자 이면 0은 중복된 숫자 입니다.

그러면 세번째 숫자를 비교 합니다. 세번째 숫자 1 과 두번째 숫자 0은 같지 않기 때문에 1을 두번째 자리에 놓습니다.

 

그러면 이제 0,1,1,1,1,2,2,3,3,4 가 됩니다. 처음 입력값은 0,0,1,1,1,2,2,3,3,4 이었습니다.

네번째 숫자 1은 세번째 숫자와 같습니다. 넘어 갑니다. 다섯번째 숫자도 1입니다. 넘어갑니다.

여섯번째 숫자는 2 입니다. 그 전 숫자와 다릅니다. 그러면 이 2를 세번째 자리에 넣습니다.

이제 배열은 0,1,2,1,1,2,2,3,3,4 가 됐습니다.

일곱번째 숫자는 2 입니다. 이전 숫자와 같으니 넘어가고 여덟번째 숫자는 3입니다.

그럼 이 3을 네번째 자리에 넣습니다.

0,1,2,3,1,2,2,3,3,4 이제 배열은 이렇게 됐습니다.

다음은 아홉번째 숫자 차례 3이니까 넘어가고 마지막 열번째 숫자는 4. 그 이전 3과는 다르죠.

이 4를 다섯번째 자리에 넣습니다.

이제 배열의 모든 값을 살펴 봤습니다.

배열은 이렇게 됐습니다.

0,1,2,3,4,   2,2,3,3,4

중복된 숫자를 제외하면 0,1,2,3,4 가 남으니 정답은 5개 입니다.

 

이걸 코딩 하려면 두가지 값을 다루어야 합니다.

우선 입력된 배열 속의 숫자들을 모두 살펴봐야 하니까 그 배열의 아이템 개수를 다루어야 합니다.  Array.length

다음은 새로 나온 숫자를 제자리에 넣을 때 사용할 숫자를 다루어야 합니다. InsertIndex 로 변수 이름을 정하겠습니다.

 

코딩과 결과 값은 아래와 같습니다.

 

 

입력값이 1,1,2 인 경우 1,2 가 중복된 숫자를 제외한 결과 이기 때문에 2를 리턴합니다.

입력값이 0,0,1,1,1,2,2,3,3,4 인 경우 중복된 숫자를 제외한 결과가 0,1,2,3,4 이기 때문에 5가 리턴 됩니다.

 

소스는 아래와 같습니다.

 

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length; // 배열의 아이템 개수. For 문에서 사용 됨.
        if(n == 0) {
            return 0; // 입력된 배열이 empty이면 0을 반환한다.
        }
        
        int insertIndex = 1; // 새로운 숫자를 찾았을 때 삽입할 위치. 배열의 첫번째 숫자 다음에 입력하면서 시작하기 위해 값은 1이 된다.
        
        for (int i=1; i < n; i++) { // 입력된 배열의 모든 아이템 숫자를 비교하기 위해 length만큼 for문을 돌린다.
            if(nums[i] != nums[i-1]) { // 해당 숫자가 그 이전 숫자와 같지 않으면 if 문 내의 코드를 실행한다.
                nums[insertIndex] = nums[i]; // insertIndex 위치에 해당 숫자를 insert 한다.
                insertIndex++; // insertIndex의 값을 1 증가 시킨다.
            }
        }
        return insertIndex; // insertIndex 값을 리턴한다.
    }
} 

 

이번 문제의 핵심은 새로운 배열을 생성하지 말라는 것과 중복된 숫자를 제외한 숫자들의 개수를 알아내라는 겁니다.

패턴만 잘 파악한다면 코딩하기에는 그렇게 까다롭지만 않은 문제 입니다.