제자리에서 중복 제거하기

정렬된 배열이 주어졌을 때 추가 배열 없이 각 값 하나만 남기십시오. 제자리에서 처리하면 메모리를 절약할 수 있으며, 면접에서 자주 나오는 고전적인 문제입니다. 🧹

배열이 정렬되어 있으면 모든 중복값이 같은 값 옆에 놓입니다. 따라서 전체 배열이 아니라 이웃한 값끼리만 비교하면 됩니다.

마지막으로 유지한 값을 가리키는 느린 포인터와, 앞을 훑으며 새로운 값을 찾는 빠른 포인터를 사용하십시오.

느린 포인터를 기록 위치라고 생각하십시오. 그 위치와 그 앞에 있는 모든 값은 이미 정리되어 중복이 없습니다.

빠른 포인터는 앞쪽을 읽기만 합니다. 빠르게 앞서 나가다가 아직 유지하지 않은 값을 발견했을 때만 느린 포인터에 알립니다.

a[fast]가 a[slow]와 같으면 반복값이므로 빠른 포인터만 앞으로 이동하고 아무것도 하지 않습니다. 중복값은 조용히 건너뜁니다.

a[fast]가 다르면 느린 포인터를 앞으로 이동하고 그 위치에 새 값을 복사하십시오. 이렇게 하면 기존 중복값이 새로운 고유 데이터로 덮어써집니다.

순회가 끝난 뒤 slow + 1은 배열 앞부분에 모여 있는 고유한 값의 개수입니다.

고유한 접두 부분 뒤에 있는 값은 남은 불필요한 데이터입니다. 문제에서는 처음 slow + 1개의 원소만 중요하므로 뒤쪽은 그대로 두십시오.

빈 배열에는 고유한 값이 없습니다. 시작하기 전에 n == 0인지 확인하여 배열 끝을 넘어 읽지 않도록 하십시오.

이 느린 포인터와 빠른 포인터 패턴은 O(n) 시간과 O(1)의 추가 공간으로 동작합니다. 이는 메모리 제한이 엄격할 때 정확히 필요한 방식입니다.

정렬된 배열에서 느린 포인터와 빠른 포인터를 사용해 제자리에서 중복값을 제거하고 있습니다.

정렬된 배열에서는 느린 포인터와 빠른 포인터 쌍으로 추가 공간 없이 O(n) 한 번의 순회에 중복값을 제거하고, 고유한 값의 개수로 slow + 1을 반환합니다. 🎉