[leetcode] Remove Duplicates from Sorted Array

26. 정렬된 배열에서 중복 제거

감소하지 않는 순서로 정렬된 정수 배열 번호가 주어지면 중복된 내부 요소를 제거하여 각 고유 요소가 한 번만 나타나도록 합니다. 요소의 상대적 순서는 동일하게 유지되어야 한다.

일부 언어에서는 배열 길이를 변경할 수 없으므로, 대신 배열 번호의 첫 번째 부분에 결과를 배치해야 합니다. 더 형식적으로, 중복을 제거한 후 k개의 요소가 있으면 num의 첫 번째 k개의 요소가 최종 결과를 유지해야 한다. 첫 번째 k 요소 이후에 무엇을 남겨두는지는 중요하지 않다.

최종 결과를 숫자의 첫 번째 k 슬롯에 배치한 후 k를 반환한다.

다른 배열에 추가 공간을 할당하지 마십시오. O(1)개의 추가 메모리가 있는 입력 배열을 수정하여 이 작업을 수행해야 합니다.

예 1:

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

 

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

 

 

문제정리
중복된 정수를 제거하여 고유의 값이 한 번만 나타나도록 배열을 수정하고, 수정된 배열의 길이와 배열을 출력하는 문제이다.

생각한 풀이방법
1. 중복되지않는 요소을 나타내는 포인터를 만들어준다.
2. 중복된 요소를 발견하면 해당 요소를 삭제하여 배열을 재정렬 해준다.
3. 이때, 배열의 길이가 변경되면 안되므로, 삭제된 요소 이후의 모든 요소를 한 칸씩 앞으로 이동 시켜야 한다.
4. 배열의 마지막까지 중복을 제거한다.
5. 최종적으로 배열의 길이와, 배열을 출력시킨다.

*i는 중복되지 않은 요소들이 쌓이는 위치를 나타내는 포인터이다.   
두번째 포인터 j는 배열을 순회하면서 중복을 탐색하는 역할을 한다.   
중복 요소가 발견되면 무시하고 중복되지 않은 요소가 발견되면 i를  증가시켜 i번째 위치에 포인터가 놓이도록 만들어준다. 그다음 중복되지않은 j요소를 그 자리에 넣어준다.

 

📌 작성코드 📌

function removeDuplicates(nums) {
  let i = 0;

  for(let j = 1; j < nums.length; j++) {
    if(nums[j] !== nums[i]) {
      i++;
      nums[i] = nums[j];
    }
  }
  return i + 1;
};

 

1. let i = 0; 을 초기값으로 대입해주는 이유?

i 는 중복이 제거된 배열의 길이를 추적하기 위해 사용됩니다.

함수가 실행될 때, 이 변수는 0으로 초기화되고, 중복이 제거된 배열에 추가될 새로운 요소가 발견될 때마다 1씩 증가합니다.

만약 이 변수를 사용하지 않고 중복이 제거된 배열의 길이를 추적하려면, nums 배열을 슬라이싱하거나

복사해서 새로운 배열을 만들어야 합니다.

이러한 방식은 추가 메모리를 사용하게 되므로,

제약 조건인 O(1) 추가 메모리를 사용해야 한다는 제약 조건을 만족시키지 못합니다.

 

그럼 하나의 for문과 두 개의 포인터를 사용하는 방식은 어떤 알고리즘을 풀때 사용하면 좋을까?

- 하나의 for문과 두 개의 포인터를 사용하는 방식은 주로 정렬된 배열에서 중복 요소를 제거하는 문제에서 사용됩니다.

이 방법은 중복 요소를 제거하면서도 배열의 상대적인 순서를 유지할 수 있기 때문에 유용하게 사용됩니다.

 

2. j 가 1부터 시작하는 이유는? 

현재 요소와 이전 요소를 비교하면서 중복을 제거하기 때문입니다.

만약 j 변수가 0부터 시작하면, 첫 번째 요소와 이전 요소를 비교해야 하므로 추가적인 예외처리가 필요해집니다.

따라서 j 변수를 1부터 시작하여 두 요소를 비교하는 것이 더욱 간단하고 깔끔한 코드를 작성할 수 있습니다.

 

3. nums =[1,1,2,3] 이라 가정한다면, 

nums[j]는 1, nums[i]도 1이다. 두 숫자는 같으므로 조건에 부합하지 않고, i 도 그대로 0이 된다.

또 반복문이 돌게되고, nums[j]는 1씩 증가하므로 2, nums[i]는 그대로 1이된다.

이번에는 조건이 성립되고 i는 1이된다.

nums[i]는 nums=[1, [i]] 로 i자리에 nums[j] 를 넣어준다.

(여기서 j는 2로 nums=[1,2]가 된다.)  

한번 더 반복문이 돌면 i=1, j=3이된다. 1과 3을 비교했을때 조건이 성립되고, 

i는 2가되고, nums=[1,2,[i]] 로 i자리에 nums[j]를 넣어주면 nums=[1,2,3] 이 된다. 

 

4. 마지막으로 nums 배열과, i + 1인 중복이 제거된 배열의 길이를 리턴한다.