[Easy] 정렬된 배열에서 중복 제거 - 26 Remove Duplicates from Sroted Array

오름차순으로 정렬된 정수 배열 nums가 주어졌을 때, 중복을 제거하여 각 고유한 요소가 한 번씩만 나타나도록 하세요. 요소들의 순서는 유지되어야 합니다. 그런 다음 nums에서 고유 요소의 개수를 반환하세요.

 

nums의 고유 요소의 수를 k라고 가정합니다. 다음 요구사항을 충족해야 합니다:

1. 배열 nums를 변경하여 처음 k개의 요소가 초기 nums에 존재했던 순서대로 고유 요소를 포함하도록 합니다. nums의 나머지 요소는 중요하지 않으며, nums의 크기도 중요하지 않습니다.
2. k를 반환합니다.

심사 기준은 다음 코드로 솔루션을 테스트합니다:

int[] nums = [...]; // 입력 배열
int[] expectedNums = [...]; // 올바른 길이의 예상 답안

int k = removeDuplicates(nums); // 구현한 함수를 호출

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

 

예시 1:

입력: nums = [1,1,2]

출력: 2, nums = [1,2,_]

설명: 함수는 k = 2를 반환해야 하며, nums의 처음 두 요소는 각각 1과 2여야 합니다. 반환된 k 이후의 값은 중요하지 않으므로 밑줄로 표시됩니다.

예시 2:

입력: nums = [0,0,1,1,1,2,2,3,3,4]

출력: 5, nums = [0,1,2,3,4,_,_,_,_,_]

설명: 함수는 k = 5를 반환해야 하며, nums의 처음 다섯 요소는 각각 0, 1, 2, 3, 4여야 합니다. 반환된 k 이후의 값은 중요하지 않으므로 밑줄로 표시됩니다.

제약 조건:

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100
• nums는 오름순으로 정렬되어 있습니다.

 

문제풀이

 

중요한 키 포인트는 이미 오름차순으로 정렬이 되어있다는 점입니다. 그러므로 순차적으로 배열을 탐색하면서 이전 값과 같은 값이면 다음 배열 요소를 검사하고 다른 값이 나오면 해당 요소의 값을 기록 해가면서 마지막까지 탐색을 하게되면 중복을 제거할 수 있게 됩니다.

class Solution:

    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        for i in range(len(nums)):
            if nums[i] != nums[k]:
                k += 1
                nums[k] = nums[i]

        return k + 1