LeetCode 26(Remove Duplicates from Sorted Array, Python)

1. 문제 링크

• https://leetcode.com/problems/remove-duplicates-from-sorted-array/

2. 문제 설명

• 이번엔 좋아요(13K)보다 싫어요(17.2K)가 더 많지만 그럼에도 상위에 있는 문제
• 오름차순으로 sort된 nums라는 배열이 있을 때, 중복이 없도록 array를 쌓고, unique 배열의 가장 마지막 index를 반환.
• 간단해보이지만, 전제조건이 "in-place"로, 기존의 데이터 구조를 변경하지 않고 정렬 또는 변환 작업을 수행해야 함
• 예시1) nums = [1,1,2] 일 때, nums = [1,2,_]로 변환하고, 2의 index인 1를 반환
• 예시2) nums = [0,0,1,1,1,2,2,2,3,3,4] 일 때, nums = [0,1,2,3,4,_,_,_,_]로 변환하고, 4의 index인 5를 반환

3. 처음 풀이 

• 처음에는 이중 for문 말고는 방법이 도저히 생각이 안나서, 이중 for문을 돌렸고, 2개 testcase에 대해 time limit이 걸림 
• 다시 코드를 봤을 때 해석이 바로 안될정도로 뭔가 복잡.. + time limit이 걸려서 개선이 필요 → 계속 고민하다가 다른 사람 풀이 참고

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums)==0: # nums 가 0이면 0을 반환
            return 0
        else:
            for i in range(len(nums)):
                if nums[i]==nums[-1]: # 만약 i번째 원소가 리스트의 마지막 원소랑 같으면
                    return len(set(nums)) # 중복 제거한 원소 개수 반환
                j=i+1
                while i+1 in range(len(nums)) and nums[i]==nums[i+1]: 
                	# 현재 원소와 다음 원소가 같을 때까지 반복
                    # k+=1
                    while j!=len(nums)-1 :
                    	#j와 j+1 위치에 있는 원소 교환
                        nums[j],nums[j+1]=nums[j+1],nums[j]
                        j+=1
                    j=i+1
                if i+1 in range(len(nums)) and nums[i]>nums[i+1]:
                    break

        return len(set(nums))

4. 다른 풀이 

• 심플 그 자체.
• 헷갈렸던 포인트가 두 element의 value를 바꿔버리면, 그 다음 루프에서도 영향을 주기 때문에, 그걸 추적하는 것이 어려웠음.
• 두개를 계속 교환하는 방식으로 가지 않고
  • j라는 변수를 하나 셋팅. j는 중복을 제거한 원소를 채울 위치를 나타냄
  • nums를 for문을 돌리면서 이전 element와의 값을 비교하며 중복 여부를 확인 
  • 중복이 아닐 때만, j에 값을 넣고, j를 1씩 증가시킨다
• 즉, 계속 nums의 elements들 위치를 마구 바꾸는게 아니라, 중복이 아닐 때만 nums[j]에 값을 넣는 식으로 코드가 구성됨
  • 예시) nums = [1,1,2,3,3,3,4]를 for문을 돌리게 되면, [1,2,3,4,3,3,4]로 바뀌게 됨. 

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1
        for i in range(1,len(nums)): 
            if nums[i] != nums[i-1]: 
                nums[j] = nums[i]
                j+=1
        return j

5. 배운 점 

• two pointer를 적절히 활용하자! complexity도 O(n^2)를 O(N)로 바뀌었다.