•
문제 설명 : 리스트 내 중복되는 요소를 제거
•
풀이 방법
◦
In-Place로 풀어야하는 문제이기 때문에, Two Pointer를 사용한 swap으로 풀었다.
◦
left에는 특정 숫자의 첫 중복이 시작되는 위치, right는 특정 숫자와 다른 숫자가 나타나는 첫번째 위치로 설정한다.
▪
left와 right를 swap하며, left 인덱스까지는 중복된 인덱스가 없도록 설정한다.
◦
이후 left 요소 이후는 전부 pop하여 삭제 처리한다.
•
시간 복잡도 :
•
성공 코드
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# 중복 체크를 위해서는 첫 인덱스가 아닌 두번째 인덱스부터 시작해야함
# 혹은 동일한 값만 존재하는 경우, 하나를 남겨서 pop 처리하기 위해서의 목적도 있음
left, right = 1, 1
if len(nums) < 2:
return 1
# 첫 중복이 발생하는 위치로 이동
while left < len(nums) and nums[left] != nums[left - 1]:
left += 1
right += 1
while right < len(nums):
# swap
if nums[left] != nums[right]:
nums[left], nums[right] = nums[right], nums[left]
# 다음 위치로 이동
left += 1
# 변경된 숫자와 중복이 아닌 다음 숫자까지 추가 이동
while right + 1 < len(nums) and nums[left - 1] == nums[right + 1]:
right += 1
right += 1
# left는 중복이 없는 마지막 인덱스이기 때문에, left 이후 요소는 전부 삭제
for _ in range(len(nums) - left):
nums.pop()
Python
복사