[LEETCODE 150] - 80 Remove Duplicates from Sorted Array II

LeetCode의 80번 문제인 "Remove Duplicates from Sorted Array II"를 해결하기 위한 것입니다.

이 문제에서 요구하는것은 정렬된 배열에서 최대 두 번까지의 중복된 숫자를 허용하면서

중복되지 않은 숫자의 개수를 반환하는 것이다.

전체 개념 요약

• 정렬된 배열에서
• 각 숫자가 최대 2번까지만 남도록
• in-place(추가 배열 없이) 처리하고
• 최종 유효 길이를 반환하는 알고리즘

 

정렬된 배열에서 각 숫자가 최대 2번까지만 남도록 in-place로 압축 하는 알고리즘이다

Key Findings

입력특징 : nums는 정렬된 배열이므로, 같은 값들이 연속된 구간으로 모여있다. 그래서 한값의 그룹(연속 구간)을 한 번에 처리할 수 있다.

 

핵심기법 : 투 포인터 + 빈도 카운트

 

-r(읽기 포인터) : 현재 값 그룹(중복 구간)을 스캔하며, 같은 값이 몇 번 나오는지 센다.

-l(쓰기 포인터) : 최대 2번까지 허용된 값만 앞쪽에 채워 넣는 위치를 가리킨다.

-count: 현재 값이 연속해서 몇 번 나왔는지 세는 변수.

 

문제 요구사항 충족 방식

- 각 숫자가 최대 두 번까지만 결과 배열에 남아야 한다.

 

- for i in range(min(2, count))로, 그룹의 실제 개수 count가 1이면 1번, 2 이상이면 2번만 쓰도록 제한한다.

 

- 배열을 in-place로 수정하고, nums[0...l-1] 구간에 결과가 저장된다.

 

---

정답 코드(Python)

class Solution:
	def removeDuplicates(self, nums: List[int]) -> int:
    	l, r = 0, 0
        
        while r < len(nums):
        	count = 1
            while r + 1 < len(nums) and nums[r] == nums[r + 1]:
            	r += 1
                count += 1
           
            for i in range (min(2, count)):
            	nums[l] = nums[r]
            	l += 1
            r += 1
        return l

 

Details

while r < len(nums) = 배열 끝까지 r을 이동시키면서, 각 값의 "연속 구간"을 하나씩 처리한다.

 

중복 개수 세기

count = 1

while r + 1 < len(nums) and nums[r] == nums[r + 1]:
	r += 1
    count += 1

 

현재 위치 r에서 시작해, 다음 값이 같을 동안 r을 이동시키며 count 증가.

 

이 루프가 끝나면

 

• nums[r]는 현재 그룹의 값
• count는 이 값이 몇 번 나왔는지 (연속 개수)

최대 두 번 쓰기

for i in range(min(2, count)):
	nums[l] = nums[r]
    l += 1

 

• 그룹에 실제로 count개가 있어도, 결과에는 최대 2개만 남기기 위해 min(2, count) 사용. 
• nums[l]에 현재 값 nums[r] 을 쓰고 l을 증가시켜 결과 부분 배열을 앞에서부터 채운다. 

 

다음 그룹으로 이동

r += 1

 

 

방금 처리한 값 그룹의 마지막 위치가 r 이였으므로, r += 1 해서 다음 값 그룹으로 넘어간다.

다시 while r < len(nums) 조건으로 돌아가 다음 그룹 처리.

 

반환값 l

최종적으로 nums[0..l-1] 구간이 조건을 만족하는 배열이며, 함수는 그 길이 l을 반환한다.

---

시간 복잡도 & 공간 복잡도

시간복잡도 : O(n)

 

r는 배열 전체를 한번만 오른쪽으로 진행한다.

안쪽 while과 for가 있어도, 각 원소는 r에 의해 최대 한번 방문되고,

각 원소는 l에 의해 최대 두번 쓰일뿐이라 전체 연산은 입력 크기 n에 비례한다.