문제 설명
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150
배열에서 중복은 최대 2개만 남기고 제거하는 문제
풀이
접근 방법. Two pointer
two pointer를 통해서 두개 인덱스를 조정해가면서 풀었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Approch: two pointer
#111223
ij <- 둘이 같으면 dup 1
ij <- 같으면 dup 1 업
ij <- dup가 2이상이면 j만 올림
i j <- 다른거 발견되면
ij <- i 올리고
#112123 <- 교환
i j <- 같고, dup가 2미만
ij
#112213
ij
i j <- 다른거 발견
ij <- i 올리고
#112231 <- 교환
ij <- 다른거 발견
i/j <- i 올리고 교환
j <- j 끝
위 로직처럼 i와 j를 이동해가면서 처리하다보면 중복을 최대 2개만 남기고 제거된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# nums가 없으면 그냥 0 리턴
if not nums:
return 0
i = 0
j = 1
dup = 1
while i < len(nums) and j < len(nums):
# 아이템이 같으면
if nums[i] == nums[j]:
# 연속된 아이템이 없다면 왼쪽 인덱스를 올리고 오른쪽 인덱스랑 교환
if dup < 2:
i = i + 1
nums[i], nums[j] = nums[j], nums[i]
# 연속된 아이템 있으면 오른쪽 인덱스 올리고, dup 값 올리기
j = j + 1
dup += 1
else:
i = i + 1
nums[i], nums[j] = nums[j], nums[i]
j = j + 1
dup = 1
return i + 1
위 풀이의 시간 복잡도와 공간복잡돈는 아래와 같다.
시간 복잡도 : O(N) nums만큼 루프를 도므로 O(N)
공간 복잡도 : O(1) 추가적인 공간을 사용하지 않는다.