C++로 정렬된 배열에서 중복 제거하기 – 각 원소 최대 2번까지 허용하는 방법

문제 개요

정렬된 배열 nums가 주어졌을 때, 각 중복 원소가 최대 두 번까지만 나타나도록 배열 자체(in-place)에서 중복을 제거하고, 새로운 길이를 반환해야 합니다.

이 문제의 핵심 제약 조건은 추가 공간을 사용할 수 없다는 점입니다. 즉, O(1)의 공간 복잡도만으로 문제를 해결해야 합니다.

예를 들어, 배열이 [0,0,0,1,1,1,1,2,3,3]과 같다면, 출력은 [0,0,1,1,2,3,3]이 되고, 그 길이는 7입니다.

해결 알고리즘

투 포인터(Two Pointer) 기법을 활용하면 추가 메모리 없이 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.

• len을 2로 초기화하고, n은 배열의 크기로 설정합니다.
• 배열의 크기 n이 2 이하라면, 중복 제거 없이 그대로 n을 반환합니다.
• i를 2부터 n-1까지 반복합니다.
  • 현재 원소 nums[i]가 이미 확정된 마지막 두 원소(nums[len-2], nums[len-1])와 모두 같지 않다면, 해당 원소를 nums[len] 위치에 저장하고 len을 1 증가시킵니다.
• 반복이 끝나면 len을 반환합니다.

이 방식의 핵심 아이디어는 다음과 같습니다. 새로 들어올 원소가 직전 두 원소와 동일한 값이라면 세 번 연속 등장하게 되므로 제외하고, 그렇지 않은 경우에만 결과 배열에 포함시키는 것입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int removeDuplicates(vector<int>& nums) {
      int len = 2;
      int n = nums.size();
      if(n <= 2)return n;
      for(int i = 2; i < n; i++){
         if( nums[i] != nums[len - 2] || nums[i] != nums[len - 1]){
            nums[len] = nums[i];
            len++;
         }
      }
      return len;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,0,0,1,1,1,1,2,3,3};
   cout << ob.removeDuplicates(v);
}

입력

[0,0,0,1,1,1,1,2,3,3]

출력

7

복잡도 분석

• 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
• 공간 복잡도: O(1) — 추가적인 배열이나 컨테이너를 사용하지 않고 입력 배열 내부에서 직접 처리합니다.

이 알고리즘은 LeetCode의 'Remove Duplicates from Sorted Array II' 문제와 동일한 유형으로, 정렬된 배열의 특성을 활용해 인접 원소 비교만으로 중복을 관리할 수 있다는 점이 핵심입니다.