80. Remove Duplicates from Sorted Array II

난이도: 중간 (Medium)

링크: LeetCode 80

풀이 날짜: 2025/10/15

 

1. 문제 이해

정렬된 배열 nums가 주어졌을 때, 중복된 원소가 최대 2번까지만 나타나도록 배열을 수정해야 한다.

추가 배열을 사용하지 않고 제자리(in-place) 에서 해결해야 한다.

즉, 각 원소는 최대 두 번까지만 남길 수 있고, 그 이후의 중복은 제거해야 한다.

 

2. 접근 방식

이 문제는 투 포인터(Two Pointers) 를 활용하는 전형적인 배열 조작 문제이다.

LeetCode 26번 문제(“Remove Duplicates from Sorted Array”)의 확장 버전이라고 볼 수 있다.

 

핵심 아이디어

1. k 포인터를 이용해 “결과 배열의 길이”를 관리한다.
2. 현재 원소 nums[i] 가 결과 배열의 두 칸 전(nums[k-2])과 다를 때만 새로 추가한다. 즉, nums[k-2] 와 같다면 이미 같은 원소가 2번 존재하므로 건너뛴다.
3. 배열을 순회하면서 최대 2개의 중복까지만 유지한다.

 

3. 풀이코드

var removeDuplicates = function(nums) {
  if (nums.length < 3) return nums.length; // 길이가 2 이하라면 그대로 유지

  let k = 2; // 최대 2번까지 허용

  for (let i = 2; i < nums.length; i++) {
    if (nums[i] !== nums[k - 2]) {
      nums[k] = nums[i];
      k++;
    }
  }

  return k;
};

• 시간 복잡도: O(n) — 배열을 한 번 순회한다.
• 공간 복잡도: O(1) — 추가 메모리를 사용하지 않는다.

 

시뮬레이션

nums = [0,0,1,1,1,1,2,3,3]

단계	i	nums[i]	nums[k-2]	조건	결과 (nums)	k
초기	-	-	-	-	[0,0,1,1,1,1,2,3,3]	2
2	2	1	0	✅ 다름	[0,0,1,1,1,1,2,3,3]	3
3	3	1	0	✅ 다름	[0,0,1,1,1,1,2,3,3]	4
4	4	1	1	❌ 같음	(변화 없음)	4
5	5	1	1	❌ 같음	(변화 없음)	4
6	6	2	1	✅ 다름	[0,0,1,1,2,…]	5
7	7	3	1	✅ 다름	[0,0,1,1,2,3,…]	6
8	8	3	2	✅ 다름	[0,0,1,1,2,3,3]	7

최종 반환값은 k = 7이며, 결과 배열은 [0,0,1,1,2,3,3,_,_] 이 된다.

 

4. 핵심 및 마무리

• 중복 허용 개수를 일반화할 수 있다 (k - 2 → k - N 형태로 확장 가능).
• nums[i] !== nums[k - 2] 조건이 중복을 2개까지만 허용하는 핵심이다.
• in-place 조작으로 메모리 효율성이 높다.
• “중복은 두 번까지만, 나머지는 건너뛴다.” — 투 포인터로 중복 제한 처리하기